Leetcode组合总和系列——回溯（剪枝优化）+动态规划

func combinationSum2(candidates []int, target int) (result [][]int) {
	sort.Ints(candidates)
	var dfs func(res []int, currSum, index int)
	dfs = func(res []int, currSum, index int) {
		if currSum == target {
			result = append(result, append([]int(nil), res...))
			return
		}
		var set []int
		for i := index+1; i < len(candidates); i++ {
			if isExist(set, candidates[i]) {
				continue
			} else {
				set = append(set, candidates[i])
			}

			if currSum + candidates[i] > target {	//遇到红色节点，直接跳出循环，后面也无需尝试
				break
			} else {
				res = append(res, candidates[i])
				dfs(res, currSum+candidates[i], i)
				res = res[:len(res)-1]
			}
		}
	}
    var res []int
    dfs(res, 0, -1)
	return 
}

func isExist(set []int, x int) bool {
	for _, v := range set {
		if v == x {
			return true
		}
	}
	return false
}

组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii

此题的candidates数组不再由题目给出，而是由[1,9]区间里的数组成，且每种组合不存在重复的数，则每种数字只能用一次，我们还是继续采用回溯法，不同的是限制了解集中数字的个数。而且每层的回溯都从上一层访问的节点的下一个节点开始。

如果使用暴力法去回溯，将得到下面这样的一棵解空间树（由于树过大，所以右边被省略）

因为题目中规定了树的深度必须是k，红色表示不可能的解，绿色表示可行解，紫色表示到了规定的层数k，但总和小于n的情况。

观察上述的解空间树我们发现了剪枝的方法：

1. 对于红色节点之后的节点直接裁剪掉
2. 但需要注意紫色的虽然不符合题意，但由于后面可能出现正确解，所以不能剪掉
3. 根据树的深度来剪，上面两个题中都没有规定深度，此题还可以根据深度来剪，如果超过规定深度就不继续向下探索

画出剪枝后的解空间树（同样省略了右边的树结构）：

Java版本的回溯解法代码

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> res = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        trace(result,res,0,k,n);
        return result;
    }

    public void trace (List<List<Integer>> result, List<Integer> res, int curr, int k, int n) {
        if (res.size() == k && curr == n) {
            result.add(new ArrayList<>(res));
            return;
        } else if (res.size() < k && curr < n) {
            for (int i = 1; i < 10; i++) {
                int len = res.size();
                if (len == 0 || i > res.get(len - 1)) {
                    res.add(i);
                    trace(result,res,curr+i,k,n);
                    res.remove(len);
                }
            }
        } else {        //树的深度已经大于规定的k
            return;
        }
    }
}

func combinationSum3(k int, n int) (result [][]int) {
	var dfs func(res []int, currSum int)
	dfs = func(res []int, currSum int) {
		if len(res) == k && currSum == n {
			result = append(result, append([]int(nil), res...))
			return
		} else if len(res) < k && currSum < n {
			i := 1
			if len(res) > 0 {
				i = res[len(res)-1]+1
			}
			for ; i < 10; i++ {
				res = append(res, i)
				dfs(res, currSum+i)
				res = res[:len(res)-1]
			}
		} else {		//搜索的深度已经超过了k
			return
		}
	}
	var res []int
	dfs(res, 0)
	return
}

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num:nums) {
                int tmp = i - num;
                if (tmp >= 0) {
                    dp[i] += dp[tmp];
                }
            }
        }
        return dp[target];
    }
}

func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1
	for i := 1; i <= target; i++ {
		for _, v := range nums {
			tmp := i - v
			if tmp >= 0 {
				dp[i] += dp[tmp]
			}
		}
	}
	return dp[target]
}