力扣 子集

回溯基础，一题多解，不同的回朔过程。

题目

求子集中，数组的每种元素有选与不选两种状态。因此在使用dfs与回溯时把每一个元素分别进行选与不选的情况考虑即可。可以先用dfs跳过当前元素即不选然后一直深层挖下去，直到挖到最深了即等于数组长度了，由于一直没有选，则先返回一个空集。接着，进行回到上一步即回溯过程，回到上一步dfs时则会继续执行下面的语句，直到完成当前的方法再继续回溯上一步的操作。在这一题就可以在回溯过程中加入选取当前元素的操作，接着再加一层dfs目的是为了加入元素后继续选。如数组[1，2，3]，这个方法返回的顺序为[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]，因为是回朔过程中把数加进去的，然后也是由于下一步的dfs才使得子集中能够逐步加入。

一定要注意的是，加入结果集时要实例化一个新的副本path，然后再进行remove把原来add的进行恢复，这样的目的就是为了维护好原来的path，然后找到一种可能的结果就添加副本进去，接着恢复，继续用path进行构建所需子集，去找到符合结果，然后加入到ans中。

class Solution {
    private final List<List<Integer>> ans = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) { // 子集构造完毕
            ans.add(new ArrayList<>(path)); // 复制 path
            return;
        }
        
        // 不选 nums[i]
        dfs(i + 1);
        
        // 选 nums[i]
        path.add(nums[i]);
        dfs(i + 1);
        path.remove(path.size() - 1); // 恢复现场
    }
}

然后，也可以直接用循环遍历每一个元素，用dfs把可能有的数加进去。在递归的每一层，选择当前元素并继续递归。然后在递归返回时，移除已选择的元素，恢复上一步状态，进入循环准备选择下一个元素，判断下一个元素是否可以加进。当一直回到初始时，又接着原来的循环枚举下一个元素，进一步递归回溯。这个方法返回的顺序为[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]，由循环与递归回溯的顺序可理解到。

class Solution {
    private final List<List<Integer>> ans = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        ans.add(new ArrayList<>(path)); // 复制 path
        for (int j = i; j < nums.length; j++) { // 枚举选择的数字
            path.add(nums[j]);
            dfs(j + 1);
            path.remove(path.size() - 1); // 恢复现场
        }
    }
}

回溯的题会有一点绕，多练多理解。