Leetcode: Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Understand the problem:
This is an extension of the last problem. The major difference is the array contains duplicates. It asks for returning all distant subsets. 

For the input S = [1, 2, 2], if we use exactly the same approach as the last problem, what shall we get?

Solution:
Similar to the permutation II, we check the range from start to i contains duplicated numbers, if yes, simply jump to next iteration.

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) return result;
        
        Arrays.sort(num);
        
        result.add(new ArrayList<Integer>());
        ArrayList<Integer> temp = new ArrayList<Integer>();
        
        subsetsHelper(num, 0, temp, result);
        
        return result;
    }
    
    private void subsetsHelper(int[] num, int start, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) return;
        
        for (int i = start; i < num.length; i++) {
            if (!isDup(num, start, i)) {
                temp.add(num[i]);
                result.add(new ArrayList<Integer>(temp));
                subsetsHelper(num, i + 1, temp, result);
                
                temp.remove(temp.size() - 1);
            }
        }
    }
    
    private boolean isDup(int[] num, int start, int end) {
        for (int i = start; i <= end - 1; i++) {
            if (num[i] == num[end]) return true;
        }
        return false;
    }
}

Discussion:
This problem has time complexity of O(2^n), since finding all subsets of a set is a NP problem.

Summary:
The take away message is all permutation and combination questions share very similar ways of solution. Make sure to understand the details.