深度优先搜索,搜索状态为(累加和,当前位置),沿下标递增顺序搜索,保证结果中没有重复的计数
#include <iostream> #include <queue> #include <algorithm> using namespace std; int num = 0; int n; int a[20]; void dfs(int sum, int pos) { if (sum == 40) { num++; return; } else if (sum > 40) return; else { for (int i = pos; i < n; i++) dfs(sum + a[i], i+ 1);//沿下标递增方向搜索,保证不走回头路 } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { cin >> a[i]; } dfs(0, 0); cout << num<< endl; return 0; } // 64 位输出请用 printf("%lld")