Solution For Combination Sum

Problem Statement: The combination sum problem on LeetCode is a problem that requires us to find all the combinations of numbers from an input array that sum up to a target number.

Example:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Solution:

The solution to this problem can be found using recursion and backtracking. The basic idea is to try all possible combinations of the input array to check if any combination sums up to the target number. The steps involved in solving this problem are:

Step 1: Sort the input array in ascending order to ensure that we generate combinations in a specific order.

Step 2: Define a recursive function that takes the following parameters – candidates array, target, a current index to keep track of the index in the array we are currently at, a path to store the current path we are on while traversing the recursive tree, and a result list to store the valid combinations that sum up to the target.

Step 3: Inside the recursive function, check if the current sum of all the elements in the path equals the target. If yes, append the path to the result list.

Step 4: Loop through the sorted input array starting from the current index, and for each element, append it to the path and call the recursive function with the updated path and target minus the current element.

Step 5: After the recursive call, remove the last element from the path to backtrack and try the next possible combination.

Step 6: Once all possible combinations have been tried, return the result list containing all valid combinations.

Code:

def combinationSum(candidates, target):
candidates.sort()
result = []

def backtrack(current_sum, index, path):
    if(current_sum==target):
        result.append(path)

    for i in range(index, len(candidates)):
        if(current_sum + candidates[i] > target):
            break
        backtrack(current_sum + candidates[i], i, path + [candidates[i]])

backtrack(0, 0, [])
return result

Example Usage

candidates = [2,3,6,7] target = 7
print(combinationSum(candidates, target))

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

Step by Step Implementation For Combination Sum

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

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

def combinationSum(self, candidates, target):
    res = []
    candidates.sort()
    self.dfs(candidates, target, 0, [], res)
    return res

def dfs(self, candidates, target, index, path, res):
    if target < 0:
        return  # backtracking
    if target == 0:
        res.append(path)
        return
    for i in range(index, len(candidates)):
        self.dfs(candidates, target-candidates[i], i, path+[candidates[i]], res)

var combinationSum = function(candidates, target) {
    // sort the candidates array in ascending order
    candidates.sort((a, b) => a - b);
    
    // create a results array to store all the possible combinations
    const results = [];
    
    // create a helper function to find all possible combinations
    const findCombinations = (startIndex, currentSum, currentCombination) => {
        // if the current sum equals the target, then add the current combination to the results array
        if (currentSum === target) {
            results.push(currentCombination);
            return;
        }
        
        // if the current sum is greater than the target, then we have gone too far and we need to return
        if (currentSum > target) {
            return;
        }
        
        // iterate through the candidates array starting from the startIndex
        for (let i = startIndex; i < candidates.length; i++) {
            // create a copy of the current combination
            const newCombination = [...currentCombination];
            
            // add the current candidate to the new combination
            newCombination.push(candidates[i]);
            
            // find all possible combinations from the current index 
            findCombinations(i, currentSum + candidates[i], newCombination);
        }
    };
    
    // start finding combinations from index 0 with sum 0 and an empty combination
    findCombinations(0, 0, []);
    
    // return the results array
    return results;
};

vector> combinationSum(vector& candidates, int target) {
        vector> res;
        vector cur;
        dfs(candidates, target, 0, cur, res);
        return res;
    }
    
    void dfs(vector& candidates, int target, int start, vector& cur, vector>& res) {
        if (target == 0) {
            res.push_back(cur);
            return;
        }
        
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] > target) {
                break;
            }
            cur.push_back(candidates[i]);
            dfs(candidates, target - candidates[i], i, cur, res);
            cur.pop_back();
        }
    }

public IList> CombinationSum(int[] candidates, int target) { // create a list to store all of the possible combinations IList> combinations = new List>(); // create a list to store a single combination IList combination = new List(); // sort the candidates array so that it is in ascending order Array.Sort(candidates); // call the helper function to find all of the combinations helper(candidates, target, 0, combination, combinations); // return the list of combinations return combinations; } public void helper(int[] candidates, int target, int index, IList combination, IList> combinations) { // if the target is 0, that means we have found a combination that sums to the target if (target == 0) { // add the combination to the list of combinations combinations.Add(new List(combination)); } // if the target is less than 0, that means we have gone too far and need to backtrack else if (target < 0) { return; } // if the index is greater than or equal to the candidates array, that means we have // gone through all of the candidates and need to backtrack else { // iterate through the candidates array for (int i = index; i < candidates.Length; i++) { // add the current candidate to the combination combination.Add(candidates[i]); // call the helper function again, incrementing the index and decrementing the target helper(candidates, target - candidates[i], i, combination, combinations); // remove the last element from the combination since we need to // explore other combinations combination.RemoveAt(combination.Count - 1); } } }