[LeetCode]78题Subsets/子集/回溯法Backtracking+dfs详解

参考了以下的人终于搞懂了点

参考1

参考2

参考3

78 子集
  给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
  说明：解集不能包含重复的子集。
  Given a set of distinct integers, nums, return all possible subsets (the power set).
  Note: The solution set must not contain duplicate subsets.

/*思路1
 * Backtracking+dfs
 * 回溯+深度优先搜索
 * 如果要理解，看到一个解释，也可以当作：存在和不存在。
 * 外层循环逐一往中间集合 temp 中加入元素 nums[i]，使这个元素处于存在状态
 * 开始递归，递归中携带加入新元素的 temp，并且下一次循环的起始是 i 元素的下一个，因而递归中更新 i 值为 i + 1
 * 将这个从中间集合 temp 中移除，使该元素处于不存在状态
 * */

  public static List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        dfs(res, temp, nums, 0);
        return res;
    }

 

/* * 再具体点
 * 形如[1,2,3]得到
 * [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
 * 假设某一步 temp=》 tempList.add(nums[i])=>[1]
 * 在进行dfs的时候是[1]add下一层=》[1,2]=>再下一层dfs->[1,2,3]，结束后往上回溯remove 3 =>[1,2]
 * 继续回溯会变为remove 2 =>[1] 最外层remove 1 =》[]
 * 最最外层循环结束，i++,从num[1]=2开始=temp=>[2]
 * */

 private static void dfs(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
        list.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            tempList.add(nums[i]);
            dfs(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }