Recode SubsetsSnum

7月 23 2014

看到邹博写的permutation，发现参数比较有意思，是from to这种，后来想想，确实这种比较make sense，之前写的的什么selectk，k，selectn,n都非常容易在边界之类的出错，递归出口处的逻辑等等，这种非常清晰，于是
学习邹博的coding风格重写了subsetsnum 问题。

先写了一个朴素的，遍历完2^n搜索空间的朴素，from是起点，to是终点，所以这么调用Sum(a, 0,n-1,sumx);表示从a[from…to]里面找到子集和为sumx的集合，
后来发现，这样每次都去想到底是n还是n-1，出口是k>n还是k==n呢，每次都先写一个，然后拿个例子去测，还是邹博这种写法比较规范。

void Sum(int *a, int from, int to, int sumx)
{
    if(from>to)
    {
        int sum=0;
        for(int i=0;i<=to;i++)
            sum+=a[i]*select[i];
        if(sum==sumx)
        {
            for(int i=0;i<=to;i++)
                if(select[i])
                    cout<<a[i]<<" ";
            cout<<endl;
        }
    }
    else
    {
        select[from]=false;
        Sum(a,from+1,to, sumx);
        select[from]=true;
        Sum(a,from+1,to,sumx);
    }
}

一直都考虑到这种很多无用的搜索，例如之前和已经超了，还要去遍历，显然浪费了时间，于是将和<0的剪枝，但是之前写总会出问题，改成这种写法决定试试：

void Cut_Sum(int from, int to, int sumx)
{


    if(sumx<0) return;
    else if(sumx==0)
    {
        for(int i=0;i>=to;i--)
        {
            if(selectn[i])
                cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    else if(from>to)
        return;
    else
    {
        selectn[from]=false;
        Cut_Sum(from+1,to,sumx);
        selectn[from]=true;
        Cut_Sum(from+1,to,sumx-a[from]);
    }
}

后来和上面朴素的结果比一比发现又错了，递归程序改改又挂了o(╯□╰)o

1,2,3,4,5，6 sum=6
又来了阴影，打算重新模拟一遍，发现了问题，其实不是完全乱了，而是在回溯到2 4的时候，我把5 6也打印出来了，发现这时候5 6 的select都为true，难怪print出来，怎么会出这个问题，为啥原来的没有？
后来分析一遍，发现区别了，原来每次找到解都要遍历完6个数，因此后面的自然变为false了，而我现在剪枝的话，前面一开始从false到true后是没有复原到false的，然后又从0->to print出来当然误以为5 6都选上了，所以解决方案
是只把0->from-1的根据select print出来，注意是from-1，因为sum=0 是处理0->from之后得出的和，from+1还没看，所以把上面sumx=0的for改为

for(int i=from-1;i>=0;i--)

改成后面到前面是因为一道题目要求从大到小排序，我已开始把数组升序排了。
因此这是递归版剪枝的子集和问题代码，但是OJ由于时间掐的严，还是TLE了，因为递归还是很多重复调用，要改成非递归的，不过我都忘记了。。。

Posted by richard爱闹 - 7月 23 2014
如需转载，请注明：本文来自 Richard

留言