39. Combination Sum – Leetcode Solutions

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: []

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        
        def backtrack(remain, comb, start):
            # If remain is zero, we found a valid combination
            if remain == 0:
                result.append(list(comb))
                return
            # If remain is negative, this combination is not valid
            elif remain < 0:
                return
            
            # Loop through the candidates starting from the current position
            for i in range(start, len(candidates)):
                # Add the candidate to the current combination
                comb.append(candidates[i])
                # Since we can use the same element again, we call backtrack with the same start index
                backtrack(remain - candidates[i], comb, i)
                # Remove the last element to backtrack
                comb.pop()
        
        # Sort the candidates to help with pruning (not necessary but can optimize a bit)
        candidates.sort()
        # Start the backtracking process with an empty combination
        backtrack(target, [], 0)
        
        return result

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const result = [];
    
    /**
     * Helper function for backtracking
     * @param {number} remain - the remaining sum needed to reach the target
     * @param {number[]} comb - the current combination of numbers
     * @param {number} start - the current index in candidates from which to consider adding numbers to the combination
     */
    const backtrack = (remain, comb, start) => {
        // If remain is zero, we found a valid combination
        if (remain === 0) {
            result.push([...comb]); // Make a copy of comb and add it to result
            return;
        }
        // If remain is negative, this combination is not valid
        if (remain < 0) {
            return;
        }
        
        // Loop through the candidates starting from the current position
        for (let i = start; i < candidates.length; i++) {
            // Add the candidate to the current combination
            comb.push(candidates[i]);
            // Since we can use the same element again, we call backtrack with the same start index
            backtrack(remain - candidates[i], comb, i);
            // Remove the last element to backtrack
            comb.pop();
        }
    };
    
    // Sort the candidates to help with pruning (not necessary but can optimize a bit)
    candidates.sort((a, b) => a - b);
    // Start the backtracking process with an empty combination
    backtrack(target, [], 0);
    
    return result;
};

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

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>(); // Store all valid combinations
        
        // Sort the candidates array to help with pruning (not necessary but can optimize a bit)
        Arrays.sort(candidates);
        
        // Helper function for backtracking
        backtrack(candidates, target, new ArrayList<>(), 0, result);
        
        return result;
    }
    
    /**
     * Helper function for backtracking
     * @param candidates - array of candidate numbers
     * @param remain - remaining sum needed to reach the target
     * @param comb - current combination of numbers
     * @param start - current index in candidates from which to consider adding numbers to the combination
     * @param result - list to store all valid combinations
     */
    private void backtrack(int[] candidates, int remain, List<Integer> comb, int start, List<List<Integer>> result) {
        // Base case: If remain is zero, we found a valid combination
        if (remain == 0) {
            result.add(new ArrayList<>(comb)); // Make a copy of comb and add it to result
            return;
        }
        // If remain is negative or we have exhausted all candidates, this combination is not valid
        if (remain < 0 || start == candidates.length) {
            return;
        }
        
        // Loop through the candidates starting from the current position
        for (int i = start; i < candidates.length; i++) {
            // Add the current candidate to the current combination
            comb.add(candidates[i]);
            // Recursively call backtrack with the updated remain, updated combination, and the same start index
            backtrack(candidates, remain - candidates[i], comb, i, result);
            // Remove the last element to backtrack
            comb.remove(comb.size() - 1);
        }
    }
    
   
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        IList<IList<int>> result = new List<IList<int>>(); // Store all valid combinations
        
        // Sort the candidates array to help with pruning (not necessary but can optimize a bit)
        Array.Sort(candidates);
        
        // Helper function for backtracking
        Backtrack(candidates, target, new List<int>(), 0, result);
        
        return result;
    }
    
    /**
     * Helper function for backtracking
     * @param candidates - array of candidate numbers
     * @param remain - remaining sum needed to reach the target
     * @param comb - current combination of numbers
     * @param start - current index in candidates from which to consider adding numbers to the combination
     * @param result - list to store all valid combinations
     */
    private void Backtrack(int[] candidates, int remain, List<int> comb, int start, IList<IList<int>> result) {
        // Base case: If remain is zero, we found a valid combination
        if (remain == 0) {
            result.Add(new List<int>(comb)); // Make a copy of comb and add it to result
            return;
        }
        // If remain is negative or we have exhausted all candidates, this combination is not valid
        if (remain < 0 || start == candidates.Length) {
            return;
        }
        
        // Loop through the candidates starting from the current position
        for (int i = start; i < candidates.Length; i++) {
            // Add the current candidate to the current combination
            comb.Add(candidates[i]);
            // Recursively call backtrack with the updated remain, updated combination, and the same start index
            Backtrack(candidates, remain - candidates[i], comb, i, result);
            // Remove the last element to backtrack
            comb.RemoveAt(comb.Count - 1);
        }
    }
    
    

    // Helper method to print the result
    private static void PrintResult(IList<IList<int>> result) {
        foreach (var comb in result) {
            Console.Write("[");
            Console.Write(string.Join(", ", comb));
            Console.WriteLine("]");
        }
    }
}