估计面试没通过，唉

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

我这是面不过了吧？

[kera0a]

@Kvip 取的数个数不固定，
还需再套一层循环，个数 3 改成 1 到 n 每个都算一次

[kera0a]

@Kvip 并且 n 并不是 nums.count，仔细想想还挺难的

[user8341]

@gdw1986
leetcode 题目还有一个限定条件：保证组合不超过 150 种。
所以只要递归法就够了吧。

[MinQ]

num = [2,3,5,7,9]
result = []

def calc(result):
for i in range(0,5):
result.append(num[i])
if sum(result) == 13:
print(result)
result.pop()
return
elif sum(result) < 13:
calc(result)
result.pop()
return

calc(result)

python 的，这样会有重复选择的情况，比如
[2, 2, 2, 2, 2, 3]
[2, 2, 2, 2, 3, 2]
不行的话把结果存下来，再配合个剪枝，应该就行了

[MinQ]

格式丢了，这就尴尬了

[MinQ]

num = [2,3,5,7,9]
result = []


def calc(result):
____for i in range(0,5):
________result.append(num[i])
________if sum(result) == 13:
____________print(result)
____________result.pop()
____________return
________elif sum(result) < 13:
____________calc(result)
________result.pop()
____return


calc(result)

[gdw1986]

@MinQ 感觉你这个靠谱，因为猎头提示了递归，但是我没搞出你这个的结果，格式不对

[MinQ]

@gdw1986 格式的问题，下面那一版已经修正了

[gdw1986]

@MinQ 试了，厉害，应该就是这个答案

[lambdafate]

@user8341 是的，都是一类题

[bwt]

Leetcode 零钱兑换 和这个类似

[smallpython]

不知道递归的意义是什么, 用循环又容易理解, 效率也更高

[aneureka]

这个是完全背包问题🤣

[user8341]

@lambdafate

题目条件完全一样，只是要求的计算结果不同：一题要求列出所有组合，一题要求计算组合总数。

列出所有组合的这题是不是没办法用动态规划呀？

[shen132465]

@cnoder 就是这样
```
public class NSum {
static int res = 13;
static int idx = 0;
public static void main(String[] args) {
int[] arr = {2, 3, 5, 7, 9};
Stack<Integer> resStack = new Stack();
traceback(arr, 0, 0,resStack);
}

public static void traceback(int[] arr, int s,int sum,Stack<Integer> resStack){
for (int i = s; i < arr.length; i++) {
int cs = sum + arr[i];
if(cs > res){
break;
}
resStack.push(arr[i]);
if(cs == res){
System.out.println(idx++ + " - " + resStack + " - " + i + " - " + cs);
resStack.pop();
break;
}
traceback(arr,i,cs,resStack);
resStack.pop();
}
}
}
```
```
0 - [2, 2, 2, 2, 2, 3] - 1 - 13
1 - [2, 2, 2, 2, 5] - 2 - 13
2 - [2, 2, 2, 7] - 3 - 13
3 - [2, 2, 3, 3, 3] - 1 - 13
4 - [2, 2, 9] - 4 - 13
5 - [2, 3, 3, 5] - 2 - 13
6 - [3, 3, 7] - 3 - 13
7 - [3, 5, 5] - 2 - 13

[wulin]

背包吧，刷动态规划

[gdw1986]

@wulin #56 背包是什么意思？

[lu5je0]

public static List<List<Integer>> cal(int[] arr, int target) {
List<List<Integer>> results = new ArrayList<>();
func(results, new ArrayList<>(), arr, target, 0);
return results;
}

public static void func(List<List<Integer>> results, List<Integer> curList, int[] arr, int target, int start) {
int num = curList.stream().mapToInt(value -> value).sum();
if (num > target) {
return;
}

if (num == target) {
results.add(new ArrayList<>(curList));
} else {
for (int i = start; i < arr.length; i++) {
curList.add(arr[i]);
func(results, curList, arr, target, i);
curList.remove(curList.size() - 1);
}
}
}
回溯法吧

[Taikyo]

滑动窗口算法应该可以解这道题吧

[binux]

这题有更好的解法，但是暴力的解法你也没做对啊。