Combination Sum LeetCode 39 Solution

1. Recursion

Intuition

Whenever the question asks to find permutations or printing subsequences or something similar, think of recursion/backtracking. This problem uses the “pick and non-pick” approach. The idea is similar to subset sum problem.

Algorithm

We select each number from candidates array and recursively consider two possible cases:

• if(candidates[i]<target) then we have two cases:
  • The selected number is part of the solution and included in the list.
  • The selected number is not part of the solution and not included in the list.
• if(candidates[i]>target) then we have only 1 cases of not taking.

Base Case: There will be two base cases:

• if(target==0) it means we found the answer so the list that we were carrying in recursive function we will store in answer 2D list.
• if(index>=candidates.length) it means we haven’t found any possible answer so just return back.

Dry Run

We start with an empty data structure i.e. list in our case, the target value, and the index == 0. At each index, as discussed above there are two options:

1. Include the element: Add the current element to the data structure. As duplicates are allowed, remain at the same index but reduce the target by the current element’s value.
2. Exclude the element: Do not add the element and move on to the next index, keeping the target unchanged.

We recursively explore both options. When including an element, we make a recursive call at the same index after updating the target. The target value will be target-candidates[index] (if => candidates[i]<target). When excluding, the recursive call goes to the next index.

Before backtracking, we remove the element added in the previous call. This ensures we generate all permutations with and without the element at a given index.

The recursion terminates when the index>=candidates.length for a call or when target==0. The data structure then contains a valid combination summing to target.

By recursively exploring all include/exclude choices at each index, we generate all possible combinations that sum up to the target. The backtracking and removal of elements ensures correct subsets.

Code Implementation

Here is the code implementation of combination sum in C++, Java, Python.

// Combination Sum C++ Solution

#include <vector>
#include <algorithm>

class Solution {
public:
    void help(int index, std::vector<int>& nums, std::vector<int>& list, std::vector<std::vector<int>>& res, int target) {
        // Answer found, store in res 2D vector.
        if (target == 0) {
            res.push_back(list);
            return;
        }
        
        // No possible answer, return back.
        if (index == nums.size()) return;
        
        // Take call.
        if (nums[index] <= target) {
            list.push_back(nums[index]);
            help(index, nums, list, res, target - nums[index]);
            list.pop_back(); // Backtracking step.
        }
        
        // No take call.
        help(index + 1, nums, list, res, target);
    }
    
    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> res;
        std::vector<int> list;
        
        help(0, candidates, list, res, target);
        return res;
    }
};

// Combination Sum Java Solution

class Solution {
    private void help(int index, int[] nums, List<Integer> list, List<List<Integer>> res, int target){
        
        // Answer found store in res 2D list..
        if(target==0){
             res.add(new ArrayList<>(list));
            return;
        }
           
        // No possible ans.. return back...
        if(index==nums.length)
            return;

        // Take call...
        if(nums[index]<=target) {
            list.add(nums[index]);
            help(index,nums,list,res,target-nums[index]);
            list.remove(list.size()-1); // backtracking step...
        }
            // No take call...
        help(index+1,nums,list,res,target);
    }
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res= new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        
        help(0,candidates,list,res,target);
        return res;
    }
}

// Combination Sum Python Solution

class Solution:
    def help(self, index, nums, list, res, target):
        # Answer found, store in res list of lists.
        if target == 0:
            res.append(list[:])
            return
        
        # No possible answer, return back.
        if index == len(nums):
            return
        
        # Take call.
        if nums[index] <= target:
            list.append(nums[index])
            self.help(index, nums, list, res, target - nums[index])
            list.pop()  # Backtracking step.
        
        # No take call.
        self.help(index + 1, nums, list, res, target)
    
    def combinationSum(self, candidates, target):
        res = []
        self.help(0, candidates, [], res, target)
        return res