Combination Sum

Q:
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

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

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]A:

public class CombinationSum {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        // first sort the array
        Arrays.sort(candidates);
        return combinationSum(candidates,0, target);    
    }

    private ArrayList<ArrayList<Integer>> combinationSum(int[] candidates,
            int startIndex, int target) {
        // use startIndex as the first starting index of candidates, to
        // calculate the sum
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        if (target < 0 || startIndex>= candidates.length) {
            return all;
        }
        if(target == candidates[startIndex]){
            ArrayList<Integer> al = new ArrayList<Integer>();
            al.add(target);
            all.add(al);
        }
        // if we do NOT use the startIndex value
        all.addAll( combinationSum(candidates,startIndex+1, target));
        //  if we use one startIndex value
        ArrayList<ArrayList<Integer>> nextAll =  combinationSum(candidates,startIndex, target- candidates[startIndex]);
        combineResult(all,nextAll,candidates[startIndex]);
        return all;
    }

    private void combineResult(ArrayList<ArrayList<Integer>> all,
            ArrayList<ArrayList<Integer>> nextAll, int firstValue) {
        // combine the nextAll into all
        for(int i =0;i<nextAll.size();i++){
            ArrayList<Integer> al = nextAll.get(i );
            al.add(0 , firstValue);
            all.add(al);
        }
    }
}

Mistakes:
1: 利用递归调用，基础条件检验的时候，忘了检测 startIndex是否越界。
2：肏， 忘了最基本的， 当条件符合的时候，就加上，并且返回啊。    检查target 是否和第一个数字吻合。


Learned:

----------------------------------第二遍-----递归的时候， 把所有的index  after beginIndex 都用for loop遍历了一遍，造成了，极大的重复-----------------

----------------------第三遍也是 同样的错误， 哎～～～～～～～～～～～～～～～

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] A, int target) {
        Arrays.sort(A);
        return helper(A, 0, target);
    }

    private ArrayList<ArrayList<Integer>> helper(int[] A, int start, int target) {
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        if (start >= A.length || target < A[start]) 
            return all;
        
        if (target == A[start]) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            al.add(target);
            all.add(al);
            return all;
        }
        // target > A[start], we can continue to divide it
        // use A[i]
        ArrayList<ArrayList<Integer>> less1 = helper(A, start, target - A[start]);
        for (int j = 0; j < less1.size(); j++)
            less1.get(j).add(0, A[start]);
        all.addAll(less1);
        // do not use A[i];
        less1 = helper(A, start + 1, target);
        all.addAll(less1);
        return all;
    }
}