46. Subsets & 90 Subsets II

Published on April 15, 2023

Question1

This question gives us an array and let us output all its subsets.

Algorithm1

We could utilize backtracking since we need to traverse all the elements and put them in and out of to get the results.

Code1

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        helper(res, nums, new ArrayList<>(), 0);
        return res;
    }
    
    private void helper(List<List<Integer>> res, int[] nums, List<Integer> list, int start) {
        res.add(new ArrayList<>(list));
        for(int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            helper(res, nums, list, i);
            list.remove(list.size() - 1);
        }
    }
}

Question2

This question is a follow up of previous one, where we have no duplicate elements. Now we are having duplicate number and the result list need to exclude same result.

Algorithm2

Same thought, use backtracking but do more prune here. There are two ways to exclude the duplicates before this, you need to sort the input array:

Each time you put a list into result list, you check if there is duplicates and put the distinct ones to keep uniqueness. If you do not do sort, [2, 1, 2] will have [2, 1] and [1, 2] and we couldn't filter out those duplicate out.
Instead of putting the duplicates into list and check when putting into result list, we do this on iteration elements. Because we have sort out all the elements, duplicates will stay together, and we only need to check if nums[i] == nums[i - 1] thus to avoid duplication. This is more effective that the method1.

Code2

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

Code3

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        helper(res, new ArrayList<>(), nums, 0);
        return res;
    }
    
    private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, int index) {
        res.add(new ArrayList<>(list));
        for (int i = index; i < nums.length; i++) {
            if (i != index && nums[i] == nums[i - 1]) continue;
            list.add(nums[i]);
            helper(res, list, nums, i + 1);
            list.remove(list.size() - 1);
        }
    }
}