Combinational Sum

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

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

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

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

Output: [[2,2,3],[2,3,2],[3,2,2],[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.

1. Return all combinations whose sum is target, including duplicates.

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

func combinationSum(candidates []int, target int) [][]int {
	paths := [][]int{}

	var dfs func(can []int, path []int, target int)
	dfs = func(cand []int, path []int, target int){
		if target < 0 {
			return
		}
		if target == 0 {
			paths = append(paths, append([]int{}, path...))
		}
		for _, c := range cand{
			dfs(cand, append(path, c), target - c)
		}
	}

	dfs(candidates, []int{}, target)
	return paths
}

2. Return all combinations whose sum is target, exclude the duplicates.

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

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

Note: the key here is avoid using previous elements

// Leetcode 39
// https://leetcode.com/problems/combination-sum/description/
func combinationSum(candidates []int, target int) [][]int {
	paths := [][]int{}

	var dfs func(can []int, path []int, target int)
	dfs = func(cand []int, path []int, target int){
		if target < 0 {
			return
		}
		if target == 0 {
			paths = append(paths, append([]int{}, path...))
		}
		for i, c := range cand{
			// remove duplicates by ignoring previous
			dfs(cand[i:], append(path, c), target - c)
		}
	}

	dfs(candidates, []int{}, target)
	return paths
}

3. If each number in candidates may only be used ONCE in the combination, then we do not include it next time.

func combinationSum(candidates []int, target int) [][]int {
	paths := [][]int{}

	var dfs func(can []int, path []int, target int)
	dfs = func(cand []int, path []int, target int){
		if target < 0 {
			return
		}
		if target == 0 {
			paths = append(paths, append([]int{}, path...))
		}
		for i, c := range cand{
                       // i+1 make sure each number used only once.
		       dfs(cand[i+1:], append(path, c), target - c)
		}
	}

	dfs(candidates, []int{}, target)
	return paths
}

4. If there are any duplicate numbers, and use each one just once, and avoid duplicates.

// Leetcode 40 Combination Sum II
// https://leetcode.com/problems/combination-sum-ii/description/
func combinationSum(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	paths := [][]int{}

	var dfs func(can []int, path []int, target int)
	dfs = func(cand []int, path []int, target int){
		if target < 0 {
			return
		}
		if target == 0 {
			paths = append(paths, append([]int{}, path...))
		}
		for i, c := range cand{
			if i > 0 && cand[i-1] == cand[i] {
			      continue
			}              
			dfs(cand[i + 1:], append(path, c), target - c)
		}
	}

	dfs(candidates, []int{}, target)
	return paths
}

5. Now find all valid combinations of k numbers that sum up to n such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once.

// Leetcode 216
// https://leetcode.com/problems/combination-sum-iii/description/
func combinationSum3(k int, n int) [][]int {
  candidates := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
  paths := [][]int{}
  
  var dfs func(cand []int, path []int, target int)
  dfs = func(cand []int, path []int, target int){
      if target < 0 || len(path) > k {
        return
      }
      if target == 0 && len(path) == k{
        paths = append(paths, append([]int{}, path...))
        return
      }

      for i, c := range cand{
        dfs(cand[i+1:], append(path, c), target-c)
      }

  }

  dfs(candidates, []int{}, n)
  return  paths
}

6. Actually a dp problem: pick any combinations of [1,2,3] to compose 4, return 7 ways.

// Leetcode 377 
// https://leetcode.com/problems/combination-sum-iv/description/
func combinationSum4(nums []int, target int) int {
    dp := make([]int, target +1)
    
    dp[0] = 1  
    for i := 0; i < len(dp); i++{
      for j := 0; j < len(nums); j++{
        if nums[j] <= i {
          dp[i] += dp[i-nums[j]] 
        }
      }
    }

    fmt.Printf("dp=%v\n", dp)
    return dp[target]
}