1 条题解
-
0
解题思路:
本题要求找出所有使用给定列表中的数字且和为的组合,每个数字的使用次数不超过其在列表中的出现次数,组合按非递增顺序排列,结果按字典序降序输出且唯一。
关键步骤:
-
回溯算法(DFS):
- 通过深度优先搜索遍历所有可能的组合,从当前索引开始选择元素,确保组合中的元素非递增排列(因输入列表已排序)。
- 递归终止条件为当前和等于目标,此时输出组合。
-
剪枝策略:
- 避免重复组合:在每层递归中,若当前元素与下一个元素相同,则跳过后续相同元素,确保同一层只选择第一个出现的元素,避免生成重复组合(如和)。
- 提前终止:若当前和超过目标,或已处理完所有元素,则提前终止递归。
-
组合生成顺序:
- 输入列表按非递增顺序排列,DFS从当前索引开始选择元素,确保生成的组合自然满足非递增顺序。
- 递归的遍历顺序保证组合按字典序降序生成,无需额外排序。
-
去重处理:
- 通过剪枝策略跳过重复元素,确保每个组合唯一。例如,处理完第一个后,跳过后续相同的,避免在同一层递归中重复选择。
C++实现:
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,a[15],ans[15],cur,getans; void DFS(int index,int sum) { if(index>m||sum>n) return; if(sum==n) { getans=1; printf("%d",ans[0]); for(int i=1;i<cur;i++) printf("+%d",ans[i]); printf("\n"); return; } for(int i=index;i<m;i++) { ans[cur++]=a[i]; DFS(i+1,sum+a[i]); cur--; while(i<m&&a[i]==a[i+1]) i++; } } int main() { while(scanf("%d%d",&n,&m)&&(n+m)) { cur=getans=0; for(int i=0;i<m;i++) scanf("%d",&a[i]); printf("Sums of %d:\n",n); DFS(0,0); if(!getans) printf("NONE\n"); } return 0; }
-
- 1
信息
- ID
- 565
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 7
- 已通过
- 1
- 上传者