78. 子集 (opens new window)

解题思路：回溯+DFS

1.利用索引下标按序搜索

本题不要纠结在“去重”上面，因为数组不含有重复元素，DFS搜索时只需要利用索引下标即可。

具体来说，搜索长度为len的子集空间时，如果第i个位置放入的元素索引下标为index，那么后面第i+1到len个位置的元素填充时，只从索引下标在[index+1,nums.length-1]之间的元素进行查找。相当于每次查找新元素只从右边进行查找，从而保证去重。

举例：[1,2,3,4]搜索长度为3的子集时，依次结果为{1,2,3}，{1,2,4}，{1,3,4}，{2,3,4}。而对于{1,3,2}这样的结果会自动被过滤掉，因为第二个位置填入3后，第三个位置只能从3后面的元素选择。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        res.add(path);
        Set<Integer> used = new HashSet<>();
        int[] visited = new int[nums.length];
        for (int i = 1; i <= nums.length; i++) {
            dfs(res, path, nums, i, 0);
        }
        return res;
    }

    public void dfs(List<List<Integer>> res, List<Integer> path, int[] nums, int length, int start) {
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            if (length - 1 == 0) {
                res.add(new ArrayList<>(path));
            } else {
                dfs(res, path, nums, length - 1, i + 1);
            }
            path.remove(path.size() - 1);
        }
    }
}

2.优化

观察发现，在基于索引下标搜索后，整个搜索过程是有序的，从而保证不会重复填入相同元素,也就不会出现重复集合。因此每次向当前结果填入元素时，当前集合必定是唯一的。所以搜索时可以把长度限制去掉。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        res.add(path);
        Set<Integer> used = new HashSet<>();
        int[] visited = new int[nums.length];
            dfs(res, path, nums, 0);
        return res;
    }

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