回溯法求子集和问题


问题描述

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

输入

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

输出

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

样例输入

5 10
2 2 6 5 4

样例输出

2 2 6

代码实现

//
//  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;
}

结果输出


文章作者: 套陆
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 套陆 !
评论
  目录