[Recursvie][Combination][Sum][Backtracking] Combination Sum

1. Example

s= [2,3,6,7] and target 7
A solution set is :
[7]
[2,2,3]
repeated number is allowed

2. Implementation
Q1: From Combination Sum II, ?
A1: recursive + backtracking . add  recursive call .remove
2.for (i; i < ; i ++)
    .add(i)
    helper(i)
    .remove(size()-1)
return
1.Base Case
1-1 target == 0 return list of integers
1-2 target < 0 return
//1-3 i > len return
// NOTE: not len-1 since when i == len -1 we need to add
// no need for i > len since every time we call helper(i) with the same i which is bounded by the loop condition and never be greater than len


//NOTE: new ArrayList res.add( new ArrayList(item) );

// NOTE: like twoSum, threeSum need sorted Arrays.sort(candidates);

// NOTE: no duplicate start if ( i = 0 || candidates[i] != candidates[i-1]) {

// Time:O(n) over array, Space:O(n) list>
public List> combinationSum (int[] candidates, int target)
{


      List> res = new ArrayList>();
      // validate the input 
      if ( candidates == null || candidates.length == 0 )
      {
           return res;
      }

      // NOTE: like twoSum, threeSum need sorted 
      Arrays.sort(candidates);


      
      helper(candidates, 0, target, new ArrayList() ,res);
      


      return res;
}
private helper(int[] candidates, int start, int target, List item, List> res)
{     



      if ( target < 0)
         return;
      if (target == 0)
      {
         //NOTE: new ArrayList
         res.add( new ArrayList(item) );
         return;
      }




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



      return;



}

3. Similar Ones
(M) Combination Sum II
(M) Combination Sum III
(M) Letter Combinations of a Phone Number
(M) Combinations
(M) Factor Combinations