8603 子集和问题

8603 子集和问题（必做）

时间限制:1000MS  内存限制:1000K
提交次数:795 通过次数:262

题型: 编程题   语言: C++;C;VC;JAVA

Description

S是一个整数集合，S={x1,x2,...,xn}，c是一个整数。这里集合元素xi（1<=i<=n）和c都是整数，可能为负。

子集和问题就是：判断是否存在S的一个子集S1，使得：

对S集合子集树采用深度优先的顺序进行搜索，子集树从上到下每层标示着S集合中每个从左到右元素“选”或者“不选”（左1右0）。

试着用回溯算法设计解子集和问题。

 

输入格式

第一行2个数：正整数n和整数c。n表示S集合的大小（n<=100），c是子集和的目标值。
接下来一行中，有n个整数，表示集合S中的元素。

输出格式

将子集和问题的解输出，当无解时，输出"No Solution"（注意No Solution的大小写，空格，无标点）。

注意：依据S集合元素从左到右依次来画子集树，因此子集树唯一。
若存在多种子集和问题的解时，只输出在这个唯一的子集树按深度优先方向遇到的第一个解，这样保证解的唯一性，利于评判。
如：5 10
2 2 6 3 3
这里，2+2+6=10，2+2+3+3=10，但只输出2 2 6

如：5 10
2 2 3 3 6
只输出2 2 3 3

又如：5 -30
2 -2 6 -30 -3
只输出2 -2 -30

输入样例

5 10
2 2 6 5 4

输出样例

2 2 6

 

//8603  左右子树01问题

#include <iostream>

#include <stdio.h>

using namespace std;

int n,c;

int a[1000]={0};

int b[1000]={0};

int found = 0;

int res = 0;

void backtrack(int deep){ // 子集树的搜索算法，根节点，i=1

    if(found) return;  // 已经找到就返回

    if(deep > n){

    if(res == c) {

              // 搜到n-1才设置标志

            found = 1;//found 是寻找标志，找到设为true

       }

        if(found){

            for(int i=0;i<n;i++)

        {

            if(b[i]==1)

            {

                cout << a[i] <<" " ;

            }

        }

        }

    }else{

         //无条件左子树

       res += a[deep];

       b[deep]=1;

       backtrack(deep+1);

       //搜索完左子树，无条件右子树

       res -= a[deep];

       b[deep]=0;

       backtrack(deep+1);

    }

}

int main()

{

    freopen("in.txt","r",stdin);

    cin >> n >> c;;

    for(int i=0;i<n;i++){

        cin >> a[i];

    }

   backtrack(0);

   if(!found)  //注意无解的情况

    cout<<"No Solution";

    return 0;

}