在一个序列中找到m个数，它们的和为n。

Question

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

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} 的重复。我该如何更改代码，以便仅返回唯一的序列？

- Jorge Zapata

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);

- M Oehm

---

这就是我一直在寻找的答案，我知道它与索引有关，但找不到问题所在。谢谢你指出来 :) - Jorge Zapata

Answer 2

const res = allCombinations(2, 5);

const unique = res.reduce((acc, curr) => {
   const exists = acc.some(item => item.sort().toString() === curr.sort().toString());

   return exists ? acc : [...acc, curr]; 
}, []);

- Vasile Radeanu

---

谢谢你的解决方案，我实际上一直在避免过滤结果，但这肯定可以与我现有的代码配合使用。 - Jorge Zapata

Answer 3

我建议使用生成器来解决这种问题 -

1. 从 1..n 中找到解决方案
2. 大小为 m
3. 其中 q 是目标和，初始化为 n

function* solve(n, m, q = n)
{ if (m == 0 && q == 0)
    yield []
  else if (n == 0 || q < 0)
    return
  else
  { for (const s of solve(n - 1, m - 1, q - n))
      yield [...s, n]
    yield *solve(n - 1, m, q)
  }
}

for (const p of solve(5, 2))
  console.log(p)

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

我们可以通过为解决方案使用另一个默认参数s来折叠上面的for循环。

function* solve(n, m, q = n, s = [])             // s = []
{ if (m == 0 && q == 0)
    yield s
  else if (n == 0 || q < 0)
    return
  else
  { yield *solve(n - 1, m - 1, q - n, [n, ...s]) // update s
    yield *solve(n - 1, m, q, s)                 // pass s
  }
}

for (const p of solve(5, 2))
  console.log(p)

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

我们可以使用早期的return来折叠if语句 -

function* solve(n, m, q = n, s = [])
{ if (m == 0 && q == 0) return yield s  // <-
  if (n == 0 || q < 0) return
  yield *solve(n - 1, m - 1, q - n, [n, ...s])
  yield *solve(n - 1, m, q, s)
}

console.log(JSON.stringify(Array.from(solve(5,2))))
// [[1,4],[2,3]]

console.log(JSON.stringify(Array.from(solve(9,3))))
// [[1,2,6],[1,3,5],[2,3,4]]

console.log(JSON.stringify(Array.from(solve(27,6))))
// [[1,2,3,4,5,12],[1,2,3,4,6,11],[1,2,3,4,7,10],[1,2,3,5,6,10],[1,2,3,4,8,9],[1,2,3,5,7,9],[1,2,4,5,6,9],[1,2,3,6,7,8],[1,2,4,5,7,8],[1,3,4,5,6,8],[2,3,4,5,6,7]]

如果您不喜欢在“solve”上使用额外的参数，我们可以使用内部“loop”。

function solve(n, m)
{ function* loop(n, m, q, s)                   // "helper"
  { if (m == 0 && q == 0) return yield s
    if (n == 0 || q < 0) return
    yield *loop(n - 1, m - 1, q - n, [n, ...s])
    yield *loop(n - 1, m, q, s)
  }
  return loop(n, m, n, [])                     // n, m, q = n, s = []
}

console.log(JSON.stringify(Array.from(solve(5,2))))
// [[1,4],[2,3]]

console.log(JSON.stringify(Array.from(solve(9,3))))
// [[1,2,6],[1,3,5],[2,3,4]]

console.log(JSON.stringify(Array.from(solve(27,6))))
// [[1,2,3,4,5,12],[1,2,3,4,6,11],[1,2,3,4,7,10],[1,2,3,5,6,10],[1,2,3,4,8,9],[1,2,3,5,7,9],[1,2,4,5,6,9],[1,2,3,6,7,8],[1,2,4,5,7,8],[1,3,4,5,6,8],[2,3,4,5,6,7]]

如果您不喜欢它暴露生成器，您可以使用Array.from返回所有结果。

function solve(n, m)
{ function* loop(n, m, q, s)
  { if (m == 0 && q == 0) return yield s
    if (n == 0 || q < 0) return
    yield *loop(n - 1, m - 1, q - n, [n, ...s])
    yield *loop(n - 1, m, q, s)
  }
  return Array.from(loop(n, m, n, []))   // Array.from
}

console.log(JSON.stringify(solve(5,2)))  // solve now returns array
// [[1,4],[2,3]]

console.log(JSON.stringify(solve(9,3)))  // <-
// [[1,2,6],[1,3,5],[2,3,4]]

console.log(JSON.stringify(solve(27,6))) // <-
// [[1,2,3,4,5,12],[1,2,3,4,6,11],[1,2,3,4,7,10],[1,2,3,5,6,10],[1,2,3,4,8,9],[1,2,3,5,7,9],[1,2,4,5,6,9],[1,2,3,6,7,8],[1,2,4,5,7,8],[1,3,4,5,6,8],[2,3,4,5,6,7]]

随心所欲地混合使用这些技术！

- Mulan