估计面试没通过，唉

[gdw1986]

面试前猎头提示我会考递归，妈的，现学真的搞不定啊，题目是 li = [2,3,5,7,9]，输出任意组合，可以重复选，输出所有和是 13 的组合，递归现学现用失败，还是老老实实拿循环写的：
li = [2,3,5,7,9]

def sum13(li):
for i in li:
if i == 13:
print(i)
for j in li:
if i + j == 13:
print(i,j)
for k in li:
if i + j + k== 13:
print(i,j,k)
for l in li:
if i + j + k + l== 13:
print(i,j,k,l)
for o in li:
if i + j + k + l + o == 13:
print(i,j,k,l,o)

我这是面不过了吧？

[devfeng]

什么公司，测试要会动归

[gdw1986]

@devfeng 哈哈哈，一个做大数据的美企

[hello2060]

不是 dp 啦，我不知道这叫什么，模式是很常见的

```
void getall(int[] ar, int cur, List<Integer> current, List<List<Inetger>> rslt, int target) {
if (cur == ar.length) return;

if (sum(current) == target) {
rslt.add(current);
}

for (int i = cur; i < ar.length; i++) {
current.add(ar[i]);
getall(ar, i + 1, current, rslt, target); // 如果每个数只能用一次，不然就从 i 开始
current.remove(curreent.size() - 1);
}
}
```

[jmc891205]

组合的意思就是 5 个数里选 n 个，每个数只能用一次吧

[oahebky]

@georgetso
@yhxx
@gdw1986

👌 确实不是 two sum 。
这种 “不一定多少个 [加数] ” & “数组内的某一个数可以重复选” 的题目我个人还没刷到过，换我我也不会做，哈哈哈哈...

可能暴力解想想会想出来；


leetcode 只刷了一百多 medium，算法菜鸟一个；
最近找到工作入职了就暂停练算法了，所以知道自己菜，一看到算法题就问问有没有理解错题意！

[cnoder]

感觉是 dfs 求所有解 剪剪枝

[gdw1986]

@cnoder 停停，现在内卷这么严重了吗，测试都要会算法了

[boring3b]

是所有 不是最优 就该暴力来吧

[lambdafate]

leetcode 39. 组合总和问题。
可使用 dfs

```
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ret = []
candidates.sort()
self.dfs(candidates, 0, target, [], ret)
return ret

def dfs(self, candidates, index, target, path, ret):
if target == 0:
ret.append(path)
return None
for i in range(index, len(candidates)):
if candidates[i] > target:
break
self.dfs(candidates, i, target-candidates[i], path+[candidates[i]], ret)
```

[lambdafate]

@lambdafate 好家伙，直接乱格式

[8Cangtou]

回溯+剪枝

[ArthurUp]

回溯加剪枝吧

[finab]

还是用递归，时间复杂度十分感人

var result: [[Int]] = []

func comb(nums:[Int], len:Int) -> [[Int]] {
if len == 0 {
return []
}
if len == 1 {
return nums.map { [$0] }
}

var arr:[[Int]] = []
for num in nums {
for var item in comb(nums: nums, len: len - 1) {
item.append(num)
arr.append(item)
}
}
arr.forEach { (item) in
if item.reduce(0, +) == 13 {
result.append(item)
}
}
return arr
}

var nums = [2,3,5]
comb(nums: nums, len: nums.count)
print(result)

[easonHHH]

动态规划吧，定义类似一个二维数组。
先把数组排序，然后>13 的全部舍弃，方便早日跳出循环
假设数组长度为 1 [2]，那可以组合的小于 13 结果就是：[ 2:[[2]]，4:[[2,2]]，6:[[2,2,2]]，8:[[2,2,2,2]]，10:[[2,2,2,2,2]]，12:[[2,2,2,2,2,2]] ]，到 14>13 结束循环
假设数组长度为 1 [2,3]，把 2 的组合+3*N 递归出来，>13 就跳过，直到 3*N>13，结果就是：[ 2:[[2]]，[3],4:[[2,2]]，5:[[2,3]]，6:[[2,2,2],[3,3]]，7:[[2,2,3]]，8:[[2,2,2,2],[2,3,3]]，9:[[3,3,3]]，10:[[2,2,2,2,2],[2,2,3,3]]，11:[[2,2,2,2,3]]，12:[[2,2,2,2,2,2],[2,2,2,3,3],[3,3,3,3]]，13:[[2,2,2,2,2,3],[[2,2,3,3,3]] ]
手写的可能会有纰漏，然后继续，最后把二维数组[13]拉出来就行，而且好像有优化空间，你把[2,4,6,8,10,12].map(n=>{(13-n)%3==0})然后如果余数为 0 就有解的方面入手优化一下
大概思路是这样

[yaphets666]

你是测试啊? 我以为你开发呢 测试怎么考算法...

[nightcatsama]

看到输出所有组合，第一时间想到的是递归加回溯。
```js
function NSum(arr, target) {
let res = []
function dfs(start, list, total) {
if (total >= target) {
if (total === target) res.push([...list])
return
}
for (let i = start; i < arr.length; i++) {
list.push(arr[i])
dfs(i, list, total + arr[i])
list.pop()
}
}
dfs(0, [], 0)
return res
}

NSum([2,3,5,7,9], 13)
```

[user8341]

@lambdafate 确实是这道题 Combination Sum，还有 Coin Change 2 其实也是类似的吧？

leetcode.com/problems/combination-sum/

leetcode.com/problems/coin-change-2/

[zjlletian]

```
package main

import (
"fmt"
)

var items = []int{2, 3, 5, 7, 9}
var target int = 13

func main() {
findSum([]int{}, 0)
}

func findSum(list []int, sum int) {
for _, i := range items {
if sum+i > target {
return
}
newList := append(list, i)
if sum+i == target {
fmt.Println(newList)
return
}
findSum(newList, sum+i)
}
return
}
```

go 的实现

[gdw1986]

@yaphets666 说实话，听到这题，开始没觉得怎么样，越想越不对，这 TM 就是算法题吧

[Kvip]

不知道能否用第三方库完成，特意去找了下答案

```
from itertools import combinations_with_replacement
li = [2, 3, 5, 7, 9]
for item in combinations_with_replacement(li, 3):
if sum(item) == 13:
print(item)
```
输出结果：
(2, 2, 9)
(3, 3, 7)
(3, 5, 5)