class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<Integer> ans = new ArrayList<Integer>();

        Arrays.sort(candidates);

        backTrack(candidates, target, 0, ans, 0);

        return result;

    }

    public void backTrack(int[] candidates, int target, int start, List<Integer> ans, int sum){

        if(start >= candidates.length || sum + candidates[start] > target)

            return; //not found

        else if(sum + candidates[start] == target ){ //found an answer

            List<Integer> new_ans = new ArrayList<Integer>(ans); //不能用List<Integer> new_ans = ans;这个只是创建了原List的一个引用

            new_ans.add(candidates[start]);

            result.add(new_ans);

        }

        else{

            // not choose current candidate

            backTrack(candidates,target,start+1,ans,sum);

            //choose current candidate

            ans.add(candidates[start]);

            backTrack(candidates,target,start,ans,sum+candidates[start]);

            ans.remove(ans.size()-1); //List是按引用传递，为了不影响递归，需要复原

        }

    }

    private List<List<Integer>> result = new ArrayList<List<Integer>>();

}