39. 组合总和

// LeetCode指定调用方法 
public List<List<Integer>> combinationSum(int[] candidates, int target) {
		
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    backtracking(candidates, target, result, new ArrayList<>(), 0);

    return result;
}

// 回溯，记录当前candidates的开始位置
private void backtracking(int[] candidates, int target, List<List<Integer>> result, List<Integer> combinationSumList, int t) {

    if (target == 0) {
        result.add(new ArrayList<>(combinationSumList));
        return ;
    }

    for (int i = t; i < candidates.length; i++) {
        if (candidates[i] <= target) {
            combinationSumList.add(candidates[i]);
            backtracking(candidates, target - candidates[i], result, combinationSumList, i);
            combinationSumList.remove(combinationSumList.size() - 1);
        }
    }
}