My Java Solution (7ms)


  • 1
    G

    Keeping track of index is the key thing to avoid duplicates.

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

  • 0
    K

    Why do you, and many others, sort the array of candidates first?

    I think it shouldn't be necessary since we are looking at all unique combinations including repeats?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.