Combination Sum: Python JAVA and C++ Solution

Are you looking for the solution to the popular LeetCode and Interviewbit question Combination Sum? Learn the algorithm and solution for this question.

I will be discussing the solution in all three languages such as Python, JAVA, and C++. If you need the solution in other languages then provide your suggestion in the comment box.

QUESTION: Combination Sum

Given an array of distinct integers and a target integer. Return a list of all unique combinations of candidates where the chosen numbers sum to given target. You may return the combinations in any order.

The same number may be chosen unlimited times from a given array. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

In below the question, the combination for the given target is always less than 150.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Example 4:

Input: candidates = [1], target = 1
Output: [[1]]

Example 5:

Input: candidates = [1], target = 2
Output: [[1,1]]

Constraints:

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• All elements of candidates are distinct.
• 1 <= target <= 500

Solution Combination Sum Python:

We can use the backtracking approach with help of a Depth First Search^[1] algorithm to get the solution for this programming question.

Using Depth First Search Algorithm, we can check all the sum till the present element of the array and once we keep going through the array, he provides us all the combinations of such sum that is equivalent to the target.

class Solution(object):
    def combinationSum(self, candidates, target):
        ret = []
        self.depthFirstSearch(candidates, target, [], ret)
        return ret
    
    def depthFirstSearch(self, nums, target, path, ret):
        if target < 0:
            return 
        if target == 0:
            ret.append(path)
            return 
        for i in range(len(nums)):
            self.depthFirstSearch(nums[i:], target-nums[i], path+[nums[i]], ret)

Solution Of Combination Sum in JAVA

In JAVA an efficient solution, all you need is the backtracking algorithm using a depth-first search algorithm.

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{ 
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}

Solution Of Combination Sum in C++

We are going to use the same algorithm for C++ as well. There is no difference here in the logic. It depends upon you which programming language you prefer and the one which you can easily understand.

class Solution {
public:
    // it's very simple backtracking problem.
    // we could make the solution better with sorting the array .
    // so when the currcount more than the target value we skip the rest of the loop ;
    vector<int>save ;
    vector<vector<int>>mat ;
    void depthFirstSearch(int index , int count , int target , vector<int>&nums){
        if (count==target){
            mat.push_back(save) ;
            return  ;
        }
        for (int i = index ; i<nums.size()&&(target-count)>=nums[i] ; i++){
            save.push_back(nums[i]) ;
            depthFirstSearch(i , count+nums[i] , target , nums) ;
            save.pop_back() ;
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin() , candidates.end()) ;
        depthFirstSearch(0 , 0 , target, candidates) ;
        // this algo take time (2^target) like all of the nums array is ones in the worstcase ;
		// since there are two choices if we take the number or leave it ;
        // so you have to dive to the leave of the tree mean high of target ;
        // space complx is O(target) without the output answer ;
        // just the space that you need in your algo not the output one ;
        return mat ;
    }
};

That is all for this post. If you have a better solution or if you have any suggestions then provide them in the comment section. I will try to respond as earliest.

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.