组合问题解析

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

var combinationSum = function(candidates, target) {
    let res = [], n = candidates.length
    candidates.sort((a, b) => a - b)
    const backtrack = (path, sum, cur) => {
        if(sum > target) return
        else if(sum === target) res.push([...path])

        for(let i = cur; i < n; i++){ 
            path.push(candidates[i])
            backtrack(path, sum + candidates[i], i) // 关键点：每次都继续从i开始，那么就可以实现重复选取
            path.pop()
        }
    }

    backtrack([], 0, 0)
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

var combinationSum2 = function(candidates, target) {
    let res = [], n = candidates.length
    candidates.sort((a, b) => a - b) // 排序，让相同元素在一起
    const backtrack = (path, target, cur) => {
        if(target === 0) res.push([...path])
        if(cur === n || target < 0) return

        for(let i = cur; i < n; i++){
            if(i > cur && candidates[i] === candidates[i - 1]) continue // 关键点：跳过后续重复的元素
            path.push(candidates[i])
            backtrack(path, target - candidates[i], i + 1)
            path.pop()
        }
    }

    backtrack([], target, 0)
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9 每个数字
• 最多使用一次
  返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

var combinationSum3 = function(k, n) {
    let res = []
    const backtrack = (path, sum, cur) => {
        if(sum > n || path.length > k) return
        else if(sum === n && path.length === k) res.push([...path])
		// 关键点：回溯遍历的对象应该是所有剩余可选值，所以从cur开始
        for(let i = cur; i <= 9; i++){
            path.push(i)
            backtrack(path, sum + i, i + 1) // 不可以重复取值，所以传递i+1
            path.pop()
        }
    }

    backtrack([], 0, 1)
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。

/**
只要不是找路径的一律使用dp动规
 */
var combinationSum4 = function(nums, target) {
    let n = nums.length
    const dp = new Array(target + 1).fill(0)
    dp[0] = 1
    for(let i = 1; i <= target; i++){
        for(let num of nums){
            if(i >= num){
                dp[i] += dp[i - num]
            }
        }
    }
    return dp[target]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

相当于背包排列问题，需要考虑元素的排列顺序。target在外层循环，物品在内层循环