[Sum][Backtracking] Combination Sum II

1. Example

-All numbers (including target) will be positive integers.
-Elements in a combination(solution) must be non-descending order. ( i.e, a1<=a2<=a3<=..<=ak)
-No duplicate combinations(solutions).

s= [ 10,1,2,7,6,1,5] and target 8
A solution set is :
[1,7]
[1,2,5]
[2,6]
[1,1,6]



2. Implementation
Q1: Like 3Sum or 4Sum?
A1: In 3Sum or 4Sum, we fixed one or two elements and get the other two from 2Sum. However, the number of elements in a combination is non-determined.
Q1: Elements in a combination must be non-descending order ?
A1: Sorted array and pick up the number from the start
Q1: how do we backtracking ?
A1: suppose today you have an combination 1,2,5  how to back to 1 and continue look up other elements to form 1,7. So we start from every element like Word Breaker II
E.g.,
c
ca
cat + reset start and continue from s(sanddog)
E.g.,
1,1,2,5,6,7,10
1
List<Integer> item
target == 8 STOP res.add(item) => Base Case
>8 return

// Time:(2^n), Space:O(n) list>
public List> combinationSum2(int[] candidates, int target)
{
                
          List> res = new ArrayList>();
          // validate the input 
          if ( candidates == null || candidates.length == 0)
          {
              return res;
          }
          
        

          Arrays.sort(candidates);

 

          
          //for(int i = 0 ; i < candidates.length; i++)
          //{
          //       if (i==0 || candidates[i] != candidates[i-1])
          //       {
          //           List item = new ArrayList();
          //           item.add(candidates[i]);
          //           helper(candidates, i+1,target-candidates[i],item,res);
          //       }
          //}


          // NOTE: do same thing above for loop with helper, so merge it into helper for loop
          // NOTE: use new in parameter to save declare and initialize
          helper(candidates, 0, target, new ArrayList(), res);

          

          return res;
      

}

private void helper(int[] candidates,int start ,int target, Listitem, List> res)
{


          // Base Case 
          // Input:
          // [1], 1
          //Output:
          //[]
          //Expected:
          // [[1]]
          // NOTE: some solution include last element which happen in case start == length, so we have to avoid that
          if (target < 0 || start > candidates.length)
          {
                return;
          }
          if (target == 0 )
          {
                // NOTE: item is an object defined in for loop, for that one object we may have different combination
                //List newItem = new ArrayList(item);
                //res.add(newItem);
                // NOTE: inner List already create a ref, so we just need to new an object and put in
                res.add(new ArrayList(item));
                return;
          }
          





          //if (target > 0)
          //{
                for ( int i = start; i < candidates.length;i++)
                {
                    // NOTE: avoid duplicate 
                    //if (i > start && candidates[i] == candidates[i-1])
                    //{
                    //    continue;
                    //}
                    if ( i == start || candidates[i] != candidates[i-1])
                    {
                       item.add(candidates[i]);
                       helper(candidates, i+1, target - candidates[i], item, res);
                       item.remove(item.size()-1);
                    }
                }
                return;
          //}
          //return;




}

idx 0 1 2 3 4 5 6

s   1,1,2,5,6,7,10

h(1,7,"1")
     helper(2,6,"1,1")
        helper(3,4,"1,1,2")
           helper(4,-1,"1,1,2,5") return remove5
           helper(5,-2,"1,1,2,6") return remove6
           helper(6,-6,"1,1,2,10") return remove10
        return
        remove 2 
        helper(4,0,"1,1,6") Solution!
        return
        remove6
        helper(5, -1 "1,1,7")
        return 
        remove 7
        helper(6, -4 "1,1,10")
        return 
        remove 10
     return
     remove 1
     helper(3,5,"1,2")
h(2,7,"1") skip
h(3,6,"2")
h(4,3,"5")
h(5,2,"6")
h(6,1,"7")
      helper(7,-9,"7,10") return
      remove 10
return      
h(7,-2,"10") return

3. Similar Ones
Combination Sum
3Sum
4Sum