Combination Sum

Definition

Definition

The Combination Sum Algorithm finds all unique combinations of a given set of numbers that sum up to a specific target value. It's a backtracking algorithm commonly used in scenarios where you need to solve problems related to combinations and permutations

Explanation

The algorithm begins by sorting the input array to manage duplicates effectively. It then recursively traverses through potential combinations of numbers to reach the target sum. During each iteration, it chooses whether to include or exclude a number from the array in the current combination. This recursive process persists until either a combination adding up to the target is found or all possibilities are exhausted

Guidance

• Sort the input array in non-decreasing order to handle duplicates
• Initialize an empty list to store combinations
• Implement a recursive function
  • Base case: If the target sum becomes 0, add the current combination to the result list
  • Iterate through the array
    • For each element, subtract it from the target sum
    • Recursively call the function with the updated target and the remaining elements of the array
    • Remove the element from the current combination
• Call the recursive function with the initial target sum and the entire input array
• Return the list of combinations

Tips

• avoid duplicate combinations by sorting the input array and skipping duplicates during recursion
• prune the search space by stopping recursion if the current element exceeds the remaining target sum
• use a data structure like a set to store unique combinations and avoid duplicates

Practice

Practice

combinationSum(nums, target):
  sort(nums) // Sort the input array
  result = [] // Initialize result list

  backtrack(0, target, []) // Call the recursive function with initial parameters
  return result

backtrack(start, target, path):
  if target == 0:
    result.append(path) // Add current combination to result
    return

  for i from start to length(nums):
    if nums[i] > target:
      break // Stop recursion if current element exceeds target

    backtrack(i, target - nums[i], path + [nums[i]]) // Recur with updated target and path

Solution

func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    backtrack(&res, []int{}, candidates, target, 0)
    return res
}

func backtrack(res *[][]int, temp []int, candidates []int, remain int, start int) {
    if remain < 0 {
        return
    } else if remain == 0 {
        c := make([]int, len(temp))
        copy(c, temp)
        *res = append(*res, c)
        return
    } else {
        for i := start; i < len(candidates); i++ {
            temp = append(temp, candidates[i])
            backtrack(res, temp, candidates, remain-candidates[i], i)
            temp = temp[:len(temp)-1]
        }
    }
}

import java.util.*;

public 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);
      }
    }
  }
}

function combinationSum(candidates, target) {
  let result = [];
  backtrack(result, [], candidates, target, 0);
  return result;
}

function backtrack(result, tempList, candidates, remain, start) {
  if (remain < 0) {

  } else if (remain === 0) {
    result.push([...tempList]);
  } else {
    for (let i = start; i < candidates.length; i++) {
      tempList.push(candidates[i]);
      backtrack(result, tempList, candidates, remain - candidates[i], i);
      tempList.pop();
    }
  }
}

fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    backtrack(result, mutableListOf(), candidates, target, 0)
    return result
}

fun backtrack(result: MutableList<List<Int>>, tempList: MutableList<Int>, candidates: IntArray, remain: Int, start: Int) {
    if (remain < 0) {
        return
    } else if (remain == 0) {
        result.add(ArrayList(tempList))
    } else {
        for (i in start until candidates.size) {
            tempList.add(candidates[i])
            backtrack(result, tempList, candidates, remain - candidates[i], i)
            tempList.removeAt(tempList.size - 1)
        }
    }
}

def combinationSum(candidates, target):
    result = []
    backtrack(result, [], candidates, target, 0)
    return result

def backtrack(result, tempList, candidates, remain, start):
    if remain < 0:
        return
    elif remain == 0:
        result.append(list(tempList))
    else:
        for i in range(start, len(candidates)):
            tempList.append(candidates[i])
            backtrack(result, tempList, candidates, remain - candidates[i], i)
            tempList.pop()

pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    let mut result = vec![];
    backtrack(&mut result, &mut vec![], &candidates, target, 0);
    result
}

fn backtrack(result: &mut Vec<Vec<i32>>, temp_list: &mut Vec<i32>, candidates: &Vec<i32>, remain: i32, start: usize) {
    if remain < 0 {
        return;
    } else if remain == 0 {
        result.push(temp_list.clone());
    } else {
        for i in start..candidates.len() {
            temp_list.push(candidates[i]);
            backtrack(result, temp_list, candidates, remain - candidates[i], i);
            temp_list.pop();
        }
    }
}

function combinationSum(candidates: number[], target: number): number[][] {
  const result: number[][] = [];
  backtrack(result, [], candidates, target, 0);
  return result;
}

function backtrack(
  result: number[][],
  tempList: number[],
  candidates: number[],
  remain: number,
  start: number,
) {
  if (remain < 0) {
    return;
  } else if (remain === 0) {
    result.push([...tempList]);
  } else {
    for (let i = start; i < candidates.length; i++) {
      tempList.push(candidates[i]);
      backtrack(result, tempList, candidates, remain - candidates[i], i);
      tempList.pop();
    }
  }
}