子集合数问题的回溯解法

元始天尊

    这几天学回溯法，稍微有点心得了，其实就是按深度优先遍历问题解树，而分支界限法则是按广度优先遍历
    给定n=4 W={11,13,24,7} M=31   则子集合数问题的解为X={0,0,1,1} 和X={1,1,0,1}
X只能取{0 1}，相应地是选或者不选该数，按照选和不选，就可以构造一颗解树，利用回溯法遍历该树。
复杂度本应该是O(2^n)  但是由于分支裁剪以后，下面的子树都不用遍历了，所以复杂度应该远小于这个
下面是我的代码：

1. // sumofsub.cpp : Defines the entry point for the console application.
   
2. //
   
3. #include <stdio.h>
   
4. 
   
5. int main(int argc, char* argv[])
   
6. {
   
7.         int arr[6]={5,10,12,13,15,18};
   
8.         int x[6]={0,0,0,0,0,0};//0:左子树没走过 1:左子树走过，右子树没走过 2:左子树走过，右子树走过
   
9.         int sum=30;
   
10.         int totalsum=0;
    
11.         int n=6;
    
12.         for(int i=0;i<n;i++)
    
13.         {
    
14.                 totalsum+=arr[i];
    
15.         }
    
16. 
    
17.         int layer=0;
    
18. 
    
19.         while(layer>=0)
    
20.         {
    
21.                 if(totalsum >= sum)
    
22.                 {
    
23.                         if(arr[layer] == sum)
    
24.                         {
    
25.                                 for(int i=0;i<layer;i++)
    
26.                                 {
    
27.                                         if(x[i] == 1)
    
28.                                                 printf("%d ",arr[i]);
    
29.                                 }
    
30.                                 printf("%d\n",arr[layer]);
    
31.                                 x[layer]=2;
    
32.                         }
    
33.                         else if(arr[layer] < sum && x[layer] != 2)
    
34.                         {//走左子树
    
35.                                 if(x[layer] == 0)//如果左子树没走过,走左子树
    
36.                                 {
    
37.                                         x[layer]=1;
    
38.                                         sum -= arr[layer];
    
39.                                 }
    
40.                                 else
    
41.                                 {
    
42.                                         x[layer]=2;
    
43.                                         x[layer+1]=0;
    
44.                                 }
    
45.                                 totalsum -= arr[layer];
    
46.                                 layer++;
    
47.                                 continue;
    
48.                         }
    
49.                         else
    
50.                         {
    
51.                                 x[layer]=2;
    
52.                         }
    
53.                 }
    
54.                 else
    
55.                 {
    
56.                         x[layer]=2;
    
57.                 }
    
58. 
    
59.                 if(x[layer] == 2)
    
60.                 {
    
61.                         //向上层回溯
    
62.                         layer--;
    
63.                         if(layer>=0)
    
64.                         {
    
65.                                 if(x[layer] < 2)
    
66.                                         sum += arr[layer];
    
67.                                 totalsum += arr[layer];
    
68.                         }
    
69.                 }
    
70.         }
    
71. 
    
72.         getchar();
    
73.         return 0;
    
74. }
    

复制代码