对子集和问题的思考和错误记录

刚刚做了一下子集和问题，出了很多错，大概记录一下自己的调试过程
最初的代码：
思路很简单，基本就是一个类似二叉树的回溯方法，对于每一个元素都判断一次选或者不选，所以复杂度至少是2的指数级。

public class NumberAdd{
   public static void main(String[] args) {
       //int[] arr={1,3,4,2,-1,-5,46,39,30,-31,6,40,-7,9,11,23,8,-3,-4,-2};
       int[] arr={-2,1,3,8};
       int[] n={0,0};//n用来对其计数
     Add(arr,0,0,-1,n);
       System.out.println("一共有："+n[0]+"种");
    }
    static void Add(int arr[],int count,int Add_res,int res,int[] n){
       
        //System.out.println(count);
        if(count==arr.length)
          return ;
        if(Add_res==res){
            System.out.println("存在");
            n[0]++;
            n[1]=1;
          
        }
        else {
            Add(arr,count+1,Add_res,res,n);//不选
            //要选
            Add_res=Add_res+arr[count];
            
            Add(arr,count+1,Add_res,res,n);
           // if(count==0)n[1]=0;
           //if(n[1]==1)System.out.print(arr[count]+"加上");
        }
        
    }
}

这是最开始写的代码（注释部分是我调试过程的内容）
res=10的时候输出是0；显然不对
我试了试，在else里调用之前打印了Add_res值和count值,打出来是这样：

发现第一次返回的时候并没有加上arr[3]即8；分析原因在于第一次深搜到尾之后返回到count=3这一层的时候，

 Add_res=Add_res+arr[count];//这里加了8
 Add(arr,count+1,Add_res,res,n);//进入新的Add函数后，count=4，在一开始的if判断里面就退出了，
 //自然就没有走到后面的if(Add_res==res)判断，也就没有让n[0]++，因此没有计数

所以将两段if判断互相调换顺序即可
如：

public class NumberAdd{
   public static void main(String[] args) {
       //int[] arr={1,3,4,2,-1,-5,46,39,30,-31,6,40,-7,9,11,23,8,-3,-4,-2};
       int[] arr={-2,1,3,8};
       int[] n={0,0};//n用来对其计数
     Add(arr,0,0,4,n);
       System.out.println("一共有："+n[0]+"种");
    }
    static void Add(int arr[],int count,int Add_res,int res,int[] n){
        if(Add_res==res){
            System.out.println("存在");
            n[0]++;
            n[1]=1;
           
        }
        //System.out.println(count);
        if(count==arr.length)
          return ;
        else {
            System.out.println("Add_res:"+Add_res+"count:"+count);
          //System.out.print('d');
            Add(arr,count+1,Add_res,res,n);//不选
            //要选
            Add_res=Add_res+arr[count];
            
            Add(arr,count+1,Add_res,res,n);
           // if(count==0)n[1]=0;
           //if(n[1]==1)System.out.print(arr[count]+"加上");
        }   
    }
}

但是还是有输出问题，当res=4的时候，输出是两个，但是明显只有一种加法。
问题出在第一个if之后没有return，然后就继续往后面走，自然就会有在后面都不选的情况了就多了一种，所以应该在这里直接退出，加一个return
最终代码：

public class NumberAdd{
   public static void main(String[] args) {
       //int[] arr={1,3,4,2,-1,-5,46,39,30,-31,6,40,-7,9,11,23,8,-3,-4,-2};
       int[] arr={-2,1,3,8};
       int[] n={0,0};//n用来对其计数
     Add(arr,0,0,-1,n);
       System.out.println("一共有："+n[0]+"种");
    }
    static void Add(int arr[],int count,int Add_res,int res,int[] n){
        if(Add_res==res){
            System.out.println("存在");
            n[0]++;
            n[1]=1;
           return;
        }
        //System.out.println(count);
        if(count==arr.length)
          return ;
        else {
            System.out.println("Add_res:"+Add_res+"count:"+count);
          //System.out.print('d');
            Add(arr,count+1,Add_res,res,n);//不选
            //要选
            Add_res=Add_res+arr[count];
            
            Add(arr,count+1,Add_res,res,n);
           // if(count==0)n[1]=0;
           //if(n[1]==1)System.out.print(arr[count]+"加上");
        }
    }
}

接着我想打印出每种可能的子集内容。
我采用的方法是在每次函数调用的时候都生成一个在“该层”的布尔数组来标记在该层哪些数被选择了。
但是这样的空间消耗太大了吧我觉得。。（而且代码很丑）

public class NumberAdd{
   public static void main(String[] args) {
      int[] arr={1,3,4,2,-1,-5,46,39,30,-31,6,40,-7,9,11,23,8,-3,-4,-2};
      // int[] arr={-2,1,3,8};
       int[] n={0};//n用来对方案种数计数（没有指针的头疼）
       Boolean[] m;//用来标记哪些被选择了
       int num=arr.length;
       m=new Boolean[num];
       for(int i=0;i<arr.length;i++) m[i]=false;

     Add(arr,0,0,10,n,m,num);
       System.out.println("一共有："+n[0]+"种");
    }
    static void Add(int arr[],int count,int Add_res,int res,int[] n,Boolean m[],int num){
    //创建一个在每一个函数层数里面的布尔数组
        Boolean[] m_fun;
        m_fun=new Boolean[num];
        for(int i=0;i<m.length;i++){
            m_fun[i]=m[i];
        }
    //出口
        if(Add_res==res){
            System.out.println("存在");
            n[0]++;
            for(int i=0;i<m_fun.length;i++)
                if(m_fun[i])System.out.print(arr[i]+"加上");
           return;
        }
        //System.out.println(count);
        if(count==arr.length)
          return ;
       //递归执行代码
        else {
           // System.out.println("Add_res:"+Add_res+"count:"+count);
          //System.out.print('d');
            Add(arr,count+1,Add_res,res,n,m_fun,num);//不选
            //要选
            Add_res=Add_res+arr[count];
            m_fun[count]=true;
            
            Add(arr,count+1,Add_res,res,n,m_fun,num);
           // if(count==0)n[1]=0;
           //if(n[1]==1)System.out.print(arr[count]+"加上");
        }
        
    }
}

我试了试，现在在我这台电脑上跑出来是

这样的结果。还是太太慢
之后就是对运算和空间进行优化，在里面加入动态规划思想。
为什么我觉得不行呢？因为这里不是求最大，所以我岂不是每个记录都要存？检索的时间算上依然是指数级别？
比如我想的是状态转移是：每一个子集和后面其一个数讨论，如果是只判定true or false确实可以降到幂级，但是如果要算种数？？？？
或者像数梯子那样，凑出10就等于凑出9的加上凑出1的？但是。。。问题在于你不能重复选啊。。2=1+1，中间有很多种选法有重复的元素

分治？好像也不可以？额头疼。。以后再看看

最后

以上就是精明太阳为你收集整理的（算法）对子集求和问题的思考对子集和问题的思考和错误记录的全部内容，希望文章能够帮你解决（算法）对子集求和问题的思考对子集和问题的思考和错误记录所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。