javascript - 在序列中找到总和为 n 的 m 个数字

Question

给定一个从 1 到 n 的序列，我想找到所有 unique 大小为 m 且总和为 的子序列名词。子序列不需要是连续的。例如

if m = 2, n = 5
The possible unique subsequences of size 2 are {1,4} and {2,3}

到目前为止，我已经能够使用递归生成所有子序列，但我的代码并没有只返回唯一的子序列，结果中有一些重复项。

function allCombinations(m, n) {
if (m < 1) {
    return [];
}

let helper = function(m, n, arr, result, index){
    if (n < 0 || m < 0) {
        return 0;
    }

    if (m === 0 && n === 0) {
        result.push(arr.slice());
        return 1;
    }

    for (let i = index; i <= n; i++){
        arr.push(i);
        helper(m - 1, n - i, arr, result, index + 1);
        arr.pop();
    }

}

let result = [];
helper(m, n, [], result, 0);

return result;
}

和调用时

let res = allCombinations(2, 5);

结果是

[ [ 1, 4 ], [ 2, 3 ], [ 3, 2 ] ]

如您所见，{3,2} 是 {2,3} 的副本。如何更改我的代码，使其仅返回唯一序列？

Answer 1

您可以通过使用 i 而不是 index 调用递归辅助函数来强制下一个选择大于当前选择:

for (let i = index; i <= n; i++){
    arr.push(i);
    helper(m - 1, n - i, arr, result, i + 1);
    arr.pop();
}

这将产生唯一的序列，其中元素按升序排序。如果仅使用 i 调用它，则允许重复选择。

除非您从包装函数调用索引为 1 的助手，否则更改此选项将允许选择零:

let result = [];
helper(m, n, [], result, 1);