黄小华的个人网站
熬过无人问津的日子才有诗和远方!
回朔法总结之组合,全排列,子集

1 子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)

class Solution {
     List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0, new ArrayList<>());
        return res;
    }
    public void backtrack(int[] nums, int index, List<Integer> track){
        res.add(new ArrayList<>(track));
        for (int i = index; i < nums.length; i++){
            track.add(nums[i]);
            backtrack(nums, i+1, track);
            track.remove(track.size()-1);
        }
    }
}

2 子集二

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0) return ans;
        Arrays.sort(nums);
        dfs(0, nums);
        return ans;
    }
    private void dfs(int i, int[] nums) {
        if (ans.contains(tmp)) return;
        ans.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            tmp.add(nums[j]);
            dfs(j+1, nums);
            tmp.remove(tmp.size()-1);
        }
    }
}