Leetcode–Combination Sum II

The Problem:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Notes:

  1. Similar to Combination Sum, use recursion. But this time we cannot use same number repeatedly, so get a bool array to record the index of those already used.
  2. No duplicates allowed in result. Even we did the same thing of sorting the array, record the index and only examine larger number when appending to list, there is one condition could result in duplicates: the input array contains duplicates, so even the numbers in result refer to different indices in input array, they are still the same numbers. Here I used the same trick as for other duplication check–maintain a hash set of list.toString().

Java Solution

public class Solution {
    List<List<Integer>> result;
    HashSet<String> resSet;
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        result = new ArrayList<List<Integer>>();
        if(num==null || num.length==0) return result;
        Arrays.sort(num);
        resSet = new HashSet<String>();
        findTarget(num, -1, target, new ArrayList<Integer>(), new boolean[num.length]);
        return result;
    }
    
    private void findTarget(int[] num, int index, int tar, List<Integer> onelist, boolean[] used){
        for(int i = index+1; i < num.length; i++){
            if(!used[i]){
                if(tar-num[i]==0){
                    List<Integer> newlist = new ArrayList<Integer>(onelist);
                    newlist.add(num[i]);
                    if(!resSet.contains(newlist.toString())){
                        result.add(newlist);
                        resSet.add(newlist.toString());
                    }
                }
                else if(tar - num[i] > 0){
                    List<Integer> newlist = new ArrayList<Integer>(onelist);
                    newlist.add(num[i]);
                    used[i] = true;
                    findTarget(num, i, tar-num[i], newlist, used);
                    used[i] = false;
                }
            }
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s