90. Subsets II

二刷 06/2022

Version #1 Choose the next number and add the result at each layer

Time O(N* 2^N)

Space O (N)

Runtime: 2 ms, faster than 76.48% of Java online submissions for Subsets II.

Memory Usage: 43.8 MB, less than 63.83% of Java online submissions for Subsets II.

class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length == 0) {

            return result;

        }

        Arrays.sort(nums);

        dfs(nums, 0, new ArrayList<>(), result);

        return result;

    }

    

    private void dfs(int[] nums, int startIndex, List<Integer> path, List<List<Integer>> result) {

        result.add(new ArrayList<>(path));

        for (int i = startIndex; i < nums.length; i++) {

            // For the same layer, only add duplicate element once

            if (i != startIndex && nums[i] == nums[i - 1]) {

                continue;

            }

            path.add(nums[i]);

            dfs(nums, i + 1, path, result);

            path.remove(path.size() - 1);

        }

    }

}

一刷

Version #2 [TODO]
decide 1 number chosen or not at each layer


Version #1 Choosing the next number, add to result at each layer
 71.00 % 
public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        subsetsWithDupDfsHelper(nums, 0, new ArrayList<Integer>(), result);
        return result;
    }
    private void subsetsWithDupDfsHelper(int[] nums, int startIndex, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<Integer>(path));
        for (int i = startIndex; i < nums.length; i++) {
            if (i != startIndex && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
         
            subsetsWithDupDfsHelper(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}