Combination Sum I, II and III Java solution (see the similarities yourself)


  • 39
    I

    Combination Sum I

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
        return list;
    }
    
    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start) {
        if (remain < 0) return; /** no solution */
        else if (remain == 0) list.add(new ArrayList<>(tempList));
        else{
            for (int i = start; i < cand.length; i++) { 
                tempList.add(cand[i]);
                backtrack(list, tempList, cand, remain-cand[i], i);
                tempList.remove(tempList.size()-1);
            } 
        }
    
    }
    

    Combination Sum II

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
       List<List<Integer>> list = new LinkedList<List<Integer>>();
       Arrays.sort(candidates);
       backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
       return list;
    }
    
    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start) {
       
       if(remain < 0) return; /** no solution */
       else if(remain == 0) list.add(new ArrayList<>(tempList));
       else{
          for (int i = start; i < cand.length; i++) {
             if(i > start && cand[i] == cand[i-1]) continue; /** skip duplicates */
             tempList.add(cand[i]);
             backtrack(list, tempList, cand, remain - cand[i], i+1);
             tempList.remove(tempList.size() - 1);
          }
       }
    }
    

    Combination Sum III

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<Integer>(), k, n, 1);
        return list;
    }
    
    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int k, int remain, int start) {
        if(tempList.size() > k) return; /** no solution */
        else if(tempList.size() == k && remain == 0) list.add(new ArrayList<>(tempList));
        else{
            for (int i = start; i <= 9; i++) {
                tempList.add(i);
                backtrack(list, tempList, k, remain-i, i+1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

  • 1
    M
    def __init__(self):
        self.result = []
        self.candidates = []
        
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        self.candidates = candidates
        self.findCombinations(0, [], target)
        return self.result
    
    def findCombinations(self, index, data, n):
        
        if(n<0):
            return
        if(n == 0):
            self.result.append(data)
            return
        if(index==self.candidates.__len__()):
            return
        visitedIndex = None
        for i in range(index,self.candidates.__len__()):
                if visitedIndex != self.candidates[i]:
                    self.findCombinations(i+1, data+[self.candidates[i]], n-self.candidates[i])
                visitedIndex = self.candidates[i]

  • 0
    R

    Hi

    Awesome compilations of all the three solutions. Could you please tell me why we need the condition "i > start" in the second combination problem where we skip duplicates?


  • 0
    L

    @issac3 Why do we need to sort the element in the First case i.e. Combination Sum 1?


  • 0
    C

    good summary, thx


  • 0
    G

    Thank you so much for summarizing the similarities in a succinct manner.

    Can anyone please state and explain the time complexity of these solutions? Would it be O(2^n)? Thanks!


  • 0
    M

Log in to reply
 

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