子集和

太过爱你忘了你带给我的痛 2022-08-05 02:59 226阅读 0赞

问题描述：

子集和问题的一个实例为<S,c>。其中S=\{x1,x2,…,xn\}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1中所有元素的和为c。

试设计一个解子集和问题的回溯法。

问题分析：将问题的所有解空间进行构造，得到一棵二叉树。因此，可以采用暴力求解和回溯法求解。

样例输入：

5 10

2 2 65 4

样例输出：

2 2 6

参考代码：

<span style="font-family:KaiTi_GB2312;font-size:18px;">//暴力搜索 
    #include <stdio.h>
    #include <math.h>
    
    int main()
    {
    
    	int i,j;
    	int n,c;
    	int *s;
    	int temp,sum;
    
    	scanf("%d%d",&n,&c);
    	s=new int [n];
    
    	for(i=0;i<n;i++){
    		scanf("%d",&s[i]);
    	}
    
    	for(i=0;i<pow(2,n);i++)
    	{
    		temp=i; sum=0;
    		for(j=0;j<n;j++)
    		{
    			if(temp%2)
    				sum+=s[j];
    			temp=temp/2;
    		}
    
    		if(sum==c)
    		{
    			temp=i;
    			for(j=0;j<n;j++)
    			{
    				if(temp%2)
    				{
    					printf("%d\t",s[j]);
    				}
    				temp=temp/2;
    			}
    			printf("\n");
    		}
    	}
    
    	return 0;
    }
    </span>

<span style="font-family:KaiTi_GB2312;font-size:18px;">//回溯法
    #include<stdio.h>
    
    int n,sum,*arr,*mark;
    int tsum;
    
    void backtrack(int t)
    {
    	int i;
    	if(t==n){
    		if(tsum==sum){
    			for(i=0;i<n;i++)
    				if(mark[i])
    					printf("%d ",arr[i]);
    		putchar('\n');
    		}
    	}else{
    		tsum+=arr[t];
    		mark[t]=1;
    		backtrack(t+1);
    		tsum-=arr[t];
    		mark[t]=0;
    		backtrack(t+1);
    	}
    }
    int main()
    {
    	int i;
    	scanf("%d %d",&n,&sum);
    	arr=new int[n];
    	mark=new int[n];
    	for(i=0;i<n;i++){
    		scanf("%d",arr+i);
    		mark[i]=0;
    	}
    	tsum=0;
    
    	backtrack(0);
    
    
    	return 0;
    }
    </span>

测试结果：

![SouthEast][]

[SouthEast]: /images/20220805/02ba454619d64d42bdb5541caf75d60d.png