Combination Sum

                                            
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> combination;
        backtrack(candidates, target, 0, combination, res);
        return res;
    }
    
    void backtrack(vector<int>& candidates, int target, int start, vector<int>& combination, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(combination);
            return;
        }
        
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] <= target) {
                combination.push_back(candidates[i]);
                backtrack(candidates, target - candidates[i], i, combination, res);
                combination.pop_back();
            }
        }
    }
};

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

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
        if (remain < 0) {
            return;
        } else if (remain == 0) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < candidates.length; i++) {
                tempList.add(candidates[i]);
                backtrack(result, tempList, candidates, remain - candidates[i], i);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

                                            
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def backtrack(remain, path, start):
            if remain == 0:
                res.append(path[:])
                return
            if remain < 0:
                return
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtrack(remain - candidates[i], path, i)
                path.pop()
        
        res = []
        backtrack(target, [], 0)
        return res

                                            
public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        IList<IList<int>> result = new List<IList<int>>();
        IList<int> current = new List<int>();
        Backtrack(candidates, target, 0, current, result);
        return result;
    }
    
    private void Backtrack(int[] candidates, int target, int start, IList<int> current, IList<IList<int>> result) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.Add(new List<int>(current));
            return;
        }
        
        for (int i = start; i < candidates.Length; i++) {
            current.Add(candidates[i]);
            Backtrack(candidates, target - candidates[i], i, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

                                            
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const result = [];
    
    const backtrack = (current, start, target) => {
        if (target === 0) {
            result.push([...current]);
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > target) continue;
            current.push(candidates[i]);
            backtrack(current, i, target - candidates[i]);
            current.pop();
        }
    };
    
    backtrack([], 0, target);
    return result;
};

                                            
function combinationSum(candidates: number[], target: number): number[][] {
    const result: number[][] = [];
    
    const backtrack = (start: number, path: number[], target: number) => {
        if (target === 0) {
            result.push([...path]);
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > target) continue;
            path.push(candidates[i]);
            backtrack(i, path, target - candidates[i]);
            path.pop();
        }
    };
    
    backtrack(0, [], target);
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum($candidates, $target) {
        $result = [];
        $this->backtrack($candidates, $target, 0, [], $result);
        return $result;
    }

    function backtrack($candidates, $target, $start, $path, &$result) {
        if ($target < 0) {
            return;
        }
        if ($target === 0) {
            $result[] = $path;
            return;
        }
        for ($i = $start; $i < count($candidates); $i++) {
            $path[] = $candidates[$i];
            $this->backtrack($candidates, $target - $candidates[$i], $i, $path, $result);
            array_pop($path);
        }
    }
}

                                            
class Solution {
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var result = [[Int]]()
        
        func backtrack(_ target: Int, _ start: Int, _ path: [Int]) {
            if target == 0 {
                result.append(path)
                return
            }
            
            for i in start..<candidates.count {
                if candidates[i] > target {
                    continue
                }
                
                backtrack(target - candidates[i], i, path + [candidates[i]])
            }
        }
        
        backtrack(target, 0, [])
        
        return result
    }
}

                                            
class Solution {
    fun combinationSum(candidates: IntArray, target: Int): 
List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        backtrack(0, target, mutableListOf(), candidates.sorted(), result)
        return result
    }
    
    private fun backtrack(start: Int, target: Int, path: MutableList<Int>, candidates: List<Int>, result: MutableList<List<Int>>) {
        if (target == 0) {
            result.add(ArrayList(path))
            return
        }
        if (target < 0) {
            return
        }
        
        for (i in start until candidates.size) {
            path.add(candidates[i])
            backtrack(i, target - candidates[i], path, candidates, result)
            path.removeAt(path.size - 1)
        }
    }
}

                                            
class Solution {
  List<List<int>> combinationSum(List<int> candidates, int target) {
    List<List<int>> result = [];
    List<int> current = [];
    
    void backtrack(int index, int currentSum) {
      if (currentSum == target) {
        result.add(List.from(current));
        return;
      }
      
      if (currentSum > target || index == candidates.length) {
        return;
      }
      
      current.add(candidates[index]);
      backtrack(index, currentSum + candidates[index]);
      current.removeLast();
      backtrack(index + 1, currentSum);
    }
    
    backtrack(0, 0);
    
    return result;
  }
}

                                            
func combinationSum(candidates []int, target int) [][]int {
    var result [][]int
    var backtrack func(start, currentSum int, path []int)

    backtrack = func(start, currentSum int, path []int) {
        if currentSum == target {
            temp := make([]int, len(path))
            copy(temp, path)
            result = append(result, temp)
            return
        }

        if currentSum > target {
            return
        }

        for i := start; i < len(candidates); i++ {
            path = append(path, candidates[i])
            backtrack(i, currentSum+candidates[i], path)
            path = path[:len(path)-1]
        }
    }

    backtrack(0, 0, []int{})
    
    return result
}

                                            
# @param {Integer[]} candidates
# @param {Integer} target
# @return {Integer[][]}
def combination_sum(candidates, target)
    result = []
    dfs(candidates, target, [], result, 0)
    result
end

def dfs(candidates, target, path, result, index)
    if target < 0
        return
    elsif target == 0
        result << path.dup
        return
    end
    
    (index...candidates.length).each do |i|
        path << candidates[i]
        dfs(candidates, target - candidates[i], path, result, i)
        path.pop
    end
end

                                            
object Solution {
    def combinationSum(candidates: Array[Int], target: Int): List[List[Int]] = {
        def backtrack(start: Int, path: List[Int], target: Int): List[List[Int]] = {
            if (target == 0) {
                List(path)
            } else if (target < 0) {
                List()
            } else {
                var res = List[List[Int]]()
                for (i <- start until candidates.length) {
                    res = res ::: backtrack(i, path :+ candidates(i), target - candidates(i))
                }
                res
            }
        }
        
        backtrack(0, List(), target)
    }
}

                                            
impl Solution {
    pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut res = Vec::new();
        let mut path = Vec::new();
        
        Self::dfs(&candidates, target, 0, &mut path, &mut res);
        
        res
    }
    
    fn dfs(candidates: &Vec<i32>, target: i32, start: usize, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        if target == 0 {
            res.push(path.clone());
            return;
        }
        
        for i in start..candidates.len() {
            if target - candidates[i] >= 0 {
                path.push(candidates[i]);
                Self::dfs(candidates, target - candidates[i], i, path, res);
                path.pop();
            }
        }
    }
}

                                            
-spec combination_sum(Candidates :: [integer()], Target :: integer()) 
-> [[integer()]].
combination_sum(Candidates, Target) ->
    Combinations = combination_sum_helper(Candidates, Target),
    lists:usort(Combinations).

combination_sum_helper(_, 0) ->
    [[]];
combination_sum_helper([], _) ->
    [];
combination_sum_helper([C|Cs], T) when C =< T ->
    [ [C|X] || X <- combination_sum_helper([C|Cs], T-C)] ++
    combination_sum_helper(Cs, T);
combination_sum_helper([_|Cs], T) ->
    combination_sum_helper(Cs, T).

To solve this coding challenge, we need to find all unique combinations of numbers from a given list of candidates that sum up to a target value. Each number in the list can be used an unlimited number of times. Since we are asked to return all unique combinations, it's important to consider that the order of the numbers does not matter, but their frequency does. This challenge can be tackled using a backtracking approach, which is a common method for solving combinatorial problems where you need to explore all potential solutions. Here is a detailed explanation of how we can solve this problem:

Explanation

Backtracking Concept :

Backtracking is a method of constructing all (or some) solutions to computational problems, especially those including constraint satisfaction problems.
The idea involves trying to build a solution incrementally and removing solutions that fail to satisfy the constraints of the problem at any point.

Breaking Down the Problem :

We start with an empty list (or path) and an initially full target value.
We decrement the target by the selected candidate and recurse deeper with the updated target.
If at any point the target becomes zero, we have found a valid combination which we can add to our result list.
If the target becomes negative, we simply backtrack as we've exceeded the target and this path won't work.
We iterate over candidates starting with an index to ensure combinations are unique and sorted.

Detailed Steps in Pseudocode :

Define a function
combinationSum

that initializes the result list and starts the backtracking process.
Implement the backtracking function which explores all possible combinations.

Here is the pseudocode implementation:

                                            
# Main function to find all unique combinations
FUNCTION combinationSum(candidates, target):
# This will store the final valid combinations
result = []

# Inner function to perform backtracking
FUNCTION backtrack(remaining_target, current_combination, start_index):
# If we have reached the target, we found a valid combination
IF remaining_target == 0:
# Append a copy of the current combination to the result list
result.APPEND(copy_of(current_combination))
RETURN

# If the remaining target is negative, stop the exploration for this path
IF remaining_target < 0:
RETURN

# Iterate through the candidates starting from the current index
FOR i FROM start_index TO LENGTH(candidates) - 1:
# Append the candidate to the current combination
current_combination.ADD(candidates[i])

# Continue exploring with updated remaining target and current combination
# We pass 'i' to allow the same element to be reused
backtrack(remaining_target - candidates[i], current_combination, i)

# Backtrack: remove the last element to explore the next candidate
current_combination.REMOVE_LAST()

# Start the backtracking process with initial target and empty combination
backtrack(target, [], 0)

# Return the result list containing all unique combinations
RETURN result

Detailed Steps of Pseudocode

Initialization :

combinationSum

initializes an empty list
result

which will store all valid combinations.

Define Backtracking Function :

backtrack

takes
remaining_target

which tracks what is left to sum up to the target,
current_combination

which is the path of current selected numbers, and
start_index

which ensures we only explore candidates forward in the list to avoid duplicate combinations.

Base Case Valid Combination :

If the
remaining_target

equals 0, we know the current path is valid. We add a copy of this path to our results and cease further exploration down this path.

Base Case Invalid Path :

If
remaining_target

goes below 0, the path is invalid as we have exceeded the target. We return and backtrack.

Explore with Backtracking :

We loop through candidates starting from
start_index

to ensure combinations are unique.
For each candidate, we add it to the current combination and recurse with the updated target and current path.
After exploring with a candidate, we backtrack by removing the last element added.

Return Result :

After all recursive calls complete,
result

will contain all valid combinations which sum up to the target.

By carefully backtracking and using the constraints provided, we can efficiently find all possible combinations that sum up to the target.