Combination Sum II 【leetcode】

이전 문제와 달리 집합된 원소는 한 번만 사용할 수 있다.
원소 그룹을 정렬한 후, 그룹 데이터로 집합 중의 서로 다른 원소를 저장하고, 그룹 limit은 나타나는 상응하는 원소의 개수를 기록한다.
이후 방법은 유사합니다. dfs로 모든 가능한 상황을 두루 훑어보지만, 그룹 v에 대한 값을 얻을 때 원소 개수의 상한선, 즉 그룹 limit에 대응하는 값을 고려해야 합니다.
int len;
vector<int> v,limit,data;
vector<vector<int> > l;
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        len=num.size();
        sort(num.begin(),num.end());
        limit.clear();
        data.clear();
        for(int i=0,j=0,n=0;i<len;++i)
        {
            if(i==0||num[i]!=num[i-1])
            {
                if(i!=0)limit.push_back(n);
                data.push_back(num[i]);
                n=1;
                ++j;
            }
            else
                ++n;
            if(i==len-1)limit.push_back(n);
        }
        len=data.size();
        v.clear();
        l.clear();        
        if(len==0)return l;
        v.resize(len);
        hehe(0,target,data);
        return l;        
        
    }
    
    void hehe(int p,int target,vector<int > &data)
    {
      
        if(p==len)
        {
            if(target!=0)return;
            vector<int> temp;
            for(int i=0;i<len;++i)
            {
                for(int j=0;j<v[i];++j)
                    temp.push_back(data[i]);                
            }
            l.push_back(temp);
            return;
            
        }
        for(int i=0;i<=limit[p]&&data[p]*i<=target;++i)
        {
            
            v[p]=i;
            hehe(p+1,target-data[p]*i,data);
        }
        return;
    }
    
    
};

좋은 웹페이지 즐겨찾기