Unique solution sets for SubsetsSum problem

7月 31 2014

之前排列数，组合数，去除重复排列数都好了，包括next_permutation，就差去除重复组合数了。子集和问题和组合数有很多相似的地方，无非是剪枝的区别。

现在需要求数组中和等于给定值得子集，并且子集不能重复。首先采用类比思想，去除重复数的排列数无非是分析递归关系，n!=n*(n-1)!, 其中for循环进行n轮swap，重复数无非是一次交换在之前出现过，这样
n里面就会出现之前出现过的数，因此判断是否递归函数就是看从l=from->k-1 (k:from->to)里面是否存在a[l]=a[k],如果存在，这次交换就是以前出现过的，后面递归得到的解(如果有的话)也肯定是重复的。

for(k=from->to)
    swap(from,k)
    permutaion(from+1,to);
    swap(from,k)

组合数似乎复杂一些，出现重复数的时候，就会有重复solution，例如 12333345 里面3对应的select 分量如果出现 0000 0001 0011 0111 1111 分别代表单独的四个解，而其余的都是重复的，因此当遍历到最后一个
3的时候，看前面的select 4个分量是属于这5种情况，还是其他的，归纳就是k个 x，出现select x个分量是这x+1种情况，就不重复，否则会重复，不继续递归。

#define MAXNUM 100000
vector<vector<int> > allsets;
bool select[MAXNUM];
bool IsRepeatedCombination(vector<int> num, int enddup);
void SubsetsSum(vector<int> num, int from, int to, int sum)
{
    if(from>to)//all traverse
    {
        if(sum==0)
        {
            vector<int> oneset;
            for(int i=0;i<=to;i++)
            {
                if(select[i])
                    oneset.push_back(num[i]);
            }
            if(oneset.size()>0)
                allsets.push_back(oneset);
        }
    }
    else//from<=to
    {
        /*
        if(sum==0)
        {
            vector<int> oneset;
            for(int i=0;i<=from-1;i++)
            {
                if(select[i])
                    oneset.push_back(num[i]);
            }
            if(oneset.size()>0)
                allsets.push_back(oneset);
        }*/
        if(sum>=0)
        {
            select[from]=false;
            if(!IsRepeatedCombination(num,from))
                SubsetsSum(num,from+1,to,sum);
            select[from]=true;
            if(!IsRepeatedCombination(num,from))
                SubsetsSum(num,from+1,to,sum-num[from]);
        }
        else
            ;
    }
}
bool IsRepeatedCombination(vector<int> num, int enddup)
{
    if(enddup==2)
        int x=1;
    if( (enddup<=num.size()-2 && num[enddup]!=num[enddup+1]) || enddup==num.size()-1)//last duplicate element
    {
        int i=enddup;
        while(i>=1 && num[i-1]==num[enddup])
            i--;
        int startdup=i;

        i=enddup;
        while(i>=startdup && select[i]==true)
            i--;
        while(i>=startdup && select[i]==false)
            i--;
        if(i==startdup-1)
            return false;
        else
            return true;
    }
    else
        return false;
}

vector<vector<int> > combinationSum2(vector<int> &num, int target)
{
    sort(num.begin(),num.end());
    memset(select,0,num.size()*sizeof(bool));
    allsets.clear();
    SubsetsSum(num,0,num.size()-1,target);
    return allsets;
}

但是TLE，之前第一遍还犯了小错误，就是我做了剪枝，怕TLE，但是剪枝的话这种判重的算法就会出错，因为没有遍历完4个3可能就结束了，所以不能剪枝，至少我目前这个算法框架不行的。
后来将里面判连续重复数导致重复递归的函数由两遍遍历改为one-pass，当时觉得one-pass逻辑太复杂极容易有bug就没这么写，但是改成之后，还是TLE了。。。

后面用这个算法做了一道去除重复子集的全部子集问题。AC了，也是这个思路，后来记住，如果vector >如果是定义全局变量记得先初始化，可能类外面就有可能是奇怪的野值，即使类内也要记得初始化。

因此在之前3步基础上加一步，用数据从头到尾走一遍至少。

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

留言