1 条题解

  • 0
    @ 2025-5-6 5:48:44

    解题思路:

    本题要求找出所有使用给定列表中的数字且和为tt的组合,每个数字的使用次数不超过其在列表中的出现次数,组合按非递增顺序排列,结果按字典序降序输出且唯一。

    关键步骤:

    1. 回溯算法(DFS)

      • 通过深度优先搜索遍历所有可能的组合,从当前索引开始选择元素,确保组合中的元素非递增排列(因输入列表已排序)。
      • 递归终止条件为当前和等于目标tt,此时输出组合。
    2. 剪枝策略

      • 避免重复组合:在每层递归中,若当前元素与下一个元素相同,则跳过后续相同元素,确保同一层只选择第一个出现的元素,避免生成重复组合(如2+22+22+22+2)。
      • 提前终止:若当前和超过目标tt,或已处理完所有元素,则提前终止递归。
    3. 组合生成顺序

      • 输入列表按非递增顺序排列,DFS从当前索引开始选择元素,确保生成的组合自然满足非递增顺序。
      • 递归的遍历顺序保证组合按字典序降序生成,无需额外排序。
    4. 去重处理

      • 通过剪枝策略跳过重复元素,确保每个组合唯一。例如,处理完第一个22后,跳过后续相同的22,避免在同一层递归中重复选择。

    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
    上传者