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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

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.