Cacher is the code snippet organizer for pro developers

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        #if not candidates:
         #   return [[]]
        
        candidates.sort()
        res = []
        self.backtracking(candidates, target, 0, [], res)
        return res
    
    def backtracking(self, candidates, target, start, temp, res):
        if target == 0:
            return res.append(temp);
        
        for i in range(start,len(candidates)):
            if target< candidates[i]: 
                return;# Save some time
            self.backtracking(candidates, target - candidates[i], i, temp + [(candidates[i])], res) # Do not use return



"""
TESTCASES:
Input:
[2,3,6,7]
7
[2,2,2,2]
4
[1]
1
[]
0

Output:
[[2,2,3],[7]]
[[2,2],[2,2],[2,2],[2,2],[2,2],[2,2],[2,2],[2,2],[2,2],[2,2]]
[[1]]
[[]]

"""

public class Solution {
    public void backtracking(int[] candidates, int target, int start,List<Integer> temp, List<List<Integer>> res){
        if(target == 0){
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i = start; i < candidates.length; i++){
            if(target < candidates[i]) return;
            temp.add(candidates[i]);
            backtracking(candidates, target - candidates[i], i, temp, res);
            temp.remove(temp.size()-1);
            
        }
        
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        backtracking(candidates, target, 0, new ArrayList<Integer>(), res);
        return res;
    }
}