子集和问题(C语言)--回溯法

朱雀 2022-01-11 06:55 362阅读 0赞

## ***子集和问题*** ##

**题目描述**  
给定一个正整数集合X=\{x1,x2,…,xn\}和一个正整数c，设计回溯算法，求集合X的一个子集Y，使得Y中元素之和等于c。

**解题思路**  
类似于全排列的思想，尝试所有结果，如果不符合则回溯

**具体代码实现**

#include <stdio.h>
    #include <stdlib.h>
    int flag=0,sum=0;
    int *s, *x, n,c;
     
     //向文件写入一个数字 
    void fileWrite(int i){
    
    	FILE *fp;
    	fp = fopen("i:\\算法\\回溯法\\output.txt", "a");
    	
    	if (fp == NULL) {			//若打开文件失败则退出
            printf("不能打开文件！\n");
            return ;
        }
    	
    	if(i == 32767){							//如果一种解法读入完毕，则换行 
    		fprintf(fp,"\n"); 
    	}
    	else if(i<0){							//如果输入小于0则代表第几种解法 
    		fprintf(fp,"第%d种解法：",-i); 		
    	}else{
    		fprintf(fp,"%d ",i); 
    	}
    	
    	fclose(fp);	
    }
     
     //从文件读取数据 
    void fileRead(){
    	FILE *fp;
    	fp = fopen("i:\\算法\\回溯法\\input.txt", "r");
    	if (fp == NULL) {			//若打开文件失败则退出
            printf("不能打开文件！\n");
            return ;
        }
     	//从文件中读入S的大小n和子集和的目标值c 
        fscanf(fp,"%d",&n);
        fscanf(fp,"%d",&c);
    		
    	s=(int *)malloc(sizeof(int)*n);
    	x=(int *)malloc(sizeof(int)*n);
    	
    	//从文件中读取集合S中的n正整数元素
    	for(int i=0;i<n;i++){
    		fscanf(fp,"%d",&s[i]);
    		x[i]=0;
    	}
    	
    	fclose(fp);	
    } 
     
    void backtrack(int t){
    	int i;
    	if(t==n)
    	{
    		if(sum==c)
    		{
    			flag+=1;
    			fileWrite(-flag);
    			for(i=0;i<n;i++){
    				if(x[i]){
    					fileWrite(s[i]);
    				}
    			}
    				
    					
    			fileWrite(32767);
    			return;
    		}
    	}
    	else
    	{
    		sum+=s[t];
    		x[t]=1;
    		backtrack(t+1);
    		x[t]=0;
    		sum-=s[t];
    		backtrack(t+1);	
    	}
    }
    
    int main(){
    
    	fileRead(); 
    
    	backtrack(0);
    	
    	if(flag > 0){
    		printf("已将结果存入文件\n");
    	}
    	else{
    		printf("No Solution!\n");
    	} 
    	
    	return 0;
    }