回溯法求子集和问题

问题描述

子集和问题的一个实例为<S,t>。其中,S={x1,x2,x3,…,xn}是一个正整数的集合,c是一个正整数。子集和问题判定是否存在S的一个子集S1,使得 S1中的所有元素之和等于c。
试设计一个解子集和问题的回溯法。

输入

第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值。接下来的1行中,有n个正整数,表示集合S中的元素。

输出

输出子集和问题的解。当问题无解时,输出No solution!

样例输入

1
2
5 10
2 2 6 5 4

样例输出

1
2 2 6

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//
// main.c
// subset-sum
//
// Created by Canvas on 2018/12/31.
// Copyright © 2018 Canvas. All rights reserved.
//

#include <stdio.h>

#define n 5
#define c 10

int array[n]={2,2,6,5,4};
int a[n]={0};
int sum=0;
int flag=0;

void traceback(int t)
{
if(t==n){
if(sum==c){
flag=1;
for(int i=0;i<n;i++){
if(a[i]){
printf("%3d",array[i]);
}
}
printf("\n");
return;
}
}
else{
sum+=array[t];
a[t]=1;
traceback(t+1);
a[t]=0;
sum-=array[t];
traceback(t+1);
}
}

int main()
{
traceback(0);
if(!flag){
printf("No Solutions!\n");
}
return 0;
}

结果输出

-------------本文结束感谢您的阅读-------------
请站长喝杯咖啡吧´◡`