关于java:LeetCode078子集

子集

题目形容：给你一个整数数组 nums ，数组中的元素 互不雷同 。返回该数组所有可能的子集（幂集）。

解集 不能 蕴含反复的子集。你能够按 任意程序 返回解集。

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：dfs（深度优先遍历）

申明2个全局变量别离为后果集(result)和以后门路(path)，增加一个深度优先遍历的办法，该办法具体逻辑如下：

• 当k=0时，即以后门路曾经有k个数了，阐明以后门路符合条件，增加到后果集中；
• 而后遍历从1开始的数，递归调用dfs办法，调用完之后将以后门路的最初一个数从门路中去掉。

下面的处理过程和 LeetCode-077-组合 的逻辑齐全一样，区别就是本题须要遍历所有可能的元素个数(0到n之间)的组合，而后都加到后果集中。

<code class="java">import java.util.ArrayList;
import java.util.List;

public class LeetCode_078 {
    /**
     * 后果集
     */
    private static List<List<Integer>> result = new ArrayList<>();
    /**
     * 以后门路
     */
    private static List<Integer> path = new ArrayList<>();

    /**
     * 多重调用dfs(深度优先遍历)
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets(int[] nums) {
        result.add(new ArrayList<>());
        for (int i = 1; i <= nums.length; i++) {
            path = new ArrayList<>();
            dfs(0, nums, i);
        }
        return result;
    }

    /**
     * 深度优先遍历
     *
     * @param index 门路的起始地位
     * @param nums  原始的数组
     * @param k     门路剩下还须要几个值
     */
    private static void dfs(int index, int[] nums, int k) {
        if (k == 0) {
            /**
             * 以后曾经有k个值，加到后果集中
             */
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(i + 1, nums, k - 1);
            /**
             * 将以后门路的最初一个值去掉，而后持续遍历
             */
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        for (List<Integer> integers : subsets(nums)) {
            for (Integer integer : integers) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}

【每日寄语】 “坐而言，不如起而行”，在没有做出问题时，就去学去做，把实力积攒起来期待机会。

喜欢 (0)赏

[搞代码]

分享 (0)