[LeetCode#40]Combination Sum II

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, a1 ≤ a2 ≤ … ≤ 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]

Analysis:

A wrong solution:
-----------------
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<List<Integer>> ();
        if (candidates == null || candidates.length == 0 || target == 0)
            return ret;
        ArrayList<Integer> item = new ArrayList<Integer> ();
        Arrays.sort(candidates);
        for (int i = 0; i < candidates.length; i++) 
            helper(candidates, i, ret, item, target, 0);
        return ret;
    }
    
    
    public void helper(int[] candidates, int index, List<List<Integer>> ret, ArrayList<Integer> item, int target, int cur_total)     {
        if (candidates[index] + cur_total >= target) {
            return;
        } else if (candidates[index] + cur_total == target) {
            ArrayList<Integer> temp = new ArrayList<Integer> (item);
            temp.add(candidates[index]);
            ret.add(temp);
        } else {
            item.add(candidates[index]);
            for (int i = index + 1; i < candidates.length; i++)
                helper(candidates, index + 1, ret, item, target, cur_total + candidates[index]);
            item.remove(item.size() - 1);
        }
    }   
    
This solution does not take the constraint, that no duplicate combination is allowed in the result set, into consideration. 
helper(candidates, index + 1, ret, item, target, cur_total + candidates[index]);

As the same design issue in N-Queens 2, we should not try to pass the specific search direction during the recurive, that would incure a lot of child call. We should try to test each possible placement at its step. 
We should change 
form a: helper(candidates, index + 1, ret, item, target, cur_total + candidates[index]);
meaning: The next placement is candidate[index+1].
--------------------------------------------------------------------------------
item.add(candidates[index]);
for (int i = index + 1; i < candidates.length; i++)
    helper(candidates, index + 1, ret, item, target, cur_total + candidates[index]);
item.remove(item.size() - 1);

into 

form b: helper(candidates, index + 1, target-candidates[i], item, ret);
meaning: We should start try to place(add) next placement from candidates[index + 1] to candidates[length()-1].  
--------------------------------------------------------------------------------
for(int i=start;i<num.length;i++) {
    if(i>start && num[i]==num[i-1]) continue;
    item.add(num[i]);
    helper(num,i+1,target-num[i],item,res);
    tem.remove(item.size()-1);
}

Note in the form a, we have no idea weather the current placement is a duplicate or not!!!
Case : candidate: 1, 1, 1, 1, 2  target: 4
112
112 (1 result in duplicate)
1112 (no 1 is not a duplicate)
When you try to place 1 into the item, you have no idea it would result in duplicate or not.
Idea: If we could avoid the same element to be repetively placed at the same position of the reuslt string, we can avoid duplicate. 
1, 1, 1, 2 (each 1 is placed at individual position)
1, 1, 1(1), 2 (for position 2, we have already placed 1 at this position, we should never try to place 1 at this position again, otherwise, the duplicate case would happen)

In the form b, we could easily detect this situation. Casue at current search, we try to place each candiate into a specific position(item.size()). 

for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i-1]) continue;
            item.add(candidates[i]);
            helper(i+1, candidates, target-candidates[i], item, ret);
            item.remove(item.size()-1);
}

if(i>start && num[i]==num[i-1]) continue; Note the checkign i > start. try to differentiate the situation of 1, 1 with 1(1) This checking perfectly avoid the same value was placed at the same position again. It's so elegant and perfect.

Solution:

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<List<Integer>> ();
        if (candidates == null || candidates.length == 0 || target <= 0)
            return ret;
        Arrays.sort(candidates);
        ArrayList<Integer> item = new ArrayList<Integer> ();
        helper(0, candidates, target, item, ret);
        return ret;
    }
    
    public void helper(int start, int[] candidates, int target, ArrayList<Integer> item, List<List<Integer>> ret) {
        if (target == 0) {
            ret.add(new ArrayList<Integer> (item));
            return;
        }
        if (target < 0 || start >= candidates.length)
            return;
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i-1]) continue;
            item.add(candidates[i]);
            helper(i+1, candidates, target-candidates[i], item, ret);
            item.remove(item.size()-1);
        }
    }
}