组合总和 II

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

  • 输入：candidates = [10,1,2,7,6,1,5], target = 8
    输出：
    [
    [1,1,6],
    [1,2,5],
    [1,7],
    [2,6]
    ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var trainWays = function(n) {
    if (n < 2) return 1
    let p = 1
    let q = 1
    let res = 2

    for(let i = 2; i<n;i++){
        // 每一次多加一步，前面的种类都不会变，因为新加的都是一步走了就行
        // 那么只需要考虑最后一步是2步的情况，那么前面n-2的步数种类我也是知道的
        // 那么n的种类就是fn(n - 2) + fn(n - 1)的种类
        p = q
        q = res
        res = (p + q) % 1000000007
    }


    return res
};