[LeetCode] 90. Subsets II

Problem

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

BCR(Best Conceivable Runtime)

Let's say that $n$ is the number of nums. Each element in nums can be either selected or not, so the number of all possible subsets is $2^n$. Therefore the BCR is $O(2^n)$.

Solution

Let's assume that the input nums is [1, 2, 2, 3] and draw the decision tree.

At depth = 0, nums[0] = 1 can be selected or not, so there are two cases. [1] is the case that selects nums[0] and [] is the other case.

At depth = 1, nums[1] = 2 can be selected or not, so there are four cases and same thing will going to happen until the end of the tree.

But depth = 2 needs to be careful. If we select nums[2] = 2 at the red arrow case, it can be same with the sibling node [1, 2] at the left.

All descendent nodes of [1, 2] at the depth = 1 node must have [1, 2] at least. So if we select the nums[2] = 2 at the below of the [1] node at depth = 1, it will make duplicate subsets.

Therefore we need to skip all 2 at the [1] node of depth = 1. Instead of 2, nums[3] = 3 can be selected or not.

In summarize, if you select nums[i] at some depth, you need to skip all elements that are same with nums[i] for the case that you do not select nums[i].

You should keep in mind that nums must be sorted to skip all duplicate elements by linear seraching.

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        helper(nums, visited, res, 0);
        return res;
    }

    public void helper(int[] nums, boolean[] visited, List<List<Integer>> res, int idx) {
        if (idx == nums.length) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if (visited[i]) subset.add(nums[i]);
            }
            res.add(subset);
            return ;
        }
        visited[idx] = true;
        helper(nums, visited, res, idx + 1);
        visited[idx] = false;
        // skips duplicate elements
        while (idx + 1 < nums.length && nums[idx] == nums[idx + 1])
            idx += 1;
        helper(nums, visited, res, idx + 1);
    }
}

The worst case is the case that don't contain duplicate elements. So, the time complexity is $O(n*2^n)$, which is same with the basic backtracking algorithm to obtain the power set. The time complexity of sort() can be ignored because it is $O(n*logn)$.

Thoughts

백트래킹 문제를 풀때 상태 공간 트리를 그리는 연습을 더 해야겠다. 마음대로 그렸더니 이렇게 쉬운 패턴도 안보이더라..