Friday, August 29, 2014

Leetcode: Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.
  • 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:
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?

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;
        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)) {
                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;

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

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

No comments:

Post a Comment