40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/

Combination Sum II - LeetCode

 

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [   [1,2,2],   [5] ]

 

 

---

 

처음에는 완전탐색으로 풀었지만 중복된 수의 조합을 어떻게 제외할지 생각이 나지 않았다.

그래서 조합의 목록을 hash에 저장하여 중복을 방지하고자 하였다.

class HashListNode {
public:
    vector<int> vi;
 
    HashListNode* pNext, * pPrev;
};
 
HashListNode hashListNodes[5000000];
int hashListNodeIndex;
HashListNode* NewHashListNode() {
    int tmp = hashListNodeIndex;
    hashListNodeIndex++;
 
    hashListNodes[tmp].vi.clear();
    hashListNodes[tmp].pNext = 0;
    hashListNodes[tmp].pPrev = 0;
 
    return &hashListNodes[tmp];
}
 
 
class HashList {
public:
    int cnt;
    HashListNode* front, * back;
 
    void Init() {
        cnt = 0;
        front = NewHashListNode();
        back = NewHashListNode();
 
        front->pPrev = 0;
        front->pNext = back;
        back->pNext = 0;
        back->pPrev = front;
    }
 
 
    //arr이 이미 있으면 false, 없으면 추가하면서 true 를 반환한다.
    bool Insert(vector<int>& arr) {
        HashListNode* finder;
 
        for (finder = front->pNext; finder != back; finder = finder->pNext) {
            if (finder->vi == arr)
                return false;
        }
 
        HashListNode* newNode = NewHashListNode();
        newNode->vi = arr;
        HashListNode* lastNode = back->pPrev;
 
        lastNode->pNext = newNode;
        newNode->pPrev = lastNode;
 
        newNode->pNext = back;
        back->pPrev = newNode;
 
        cnt++;
 
        return true;
    }
 
};
 
class Hash {
public:
    HashList table[5000];
 
    void Init() {
        for (int i = 0; i < 5000; i++)
            table[i].Init();
    }
 
    bool Insert(vector<int>& arr) {
        int address = Hashing(arr);
        bool ret = table[address].Insert(arr);
 
        return ret;
    }
 
    int Hashing(vector<int>& arr) {
        int tmp = 0;
        for (int i = 0; i < arr.size(); i++)
            tmp = (tmp * 19 + arr[i]) % 5000;
 
        return tmp;
    }
 
};
 
 
void Init() {
    hashListNodeIndex = 0;
}
 
 
Hash hash_;
 
 
class Solution {
public:
    int tg;
    int N;
    int ret;
    vector<vector<int>> ans;
 
    void DFS(int arrSize, int sum, vector<int>& arr) {
        if (sum == tg) {
            //ans내에 ans[ans.size() - 1] 과 똑같은 행렬이 존재하는지 탐색해야 한다.
            //hash, trie, bst....
            bool ret = hash_.Insert(ans[ans.size() - 1]);
 
            //ans내에서 똑같은 조합을 찾을수 없을때만 새로 추가한다.
            if (ret == true)
                ans.push_back(ans[ans.size() - 1]);
 
            return;
        }
 
        if (sum > tg || arrSize == N)
            return;
 
        DFS(arrSize + 1, sum, arr);
 
        ans[ans.size() - 1].push_back(arr[arrSize]);
        DFS(arrSize + 1, sum + arr[arrSize], arr);
        ans[ans.size() - 1].pop_back();
 
    }
 
 
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        Init();
        hash_.Init();
 
        sort(candidates.begin(), candidates.end());
 
        N = candidates.size();
        tg = target;
        ans.clear();
 
        ans.push_back(vector<int>());
        DFS(0, 0, candidates);
        ans.pop_back();
 
        return ans;
    }
};

 

160ms에 95%라는 최악의 성능을 가지게 되었다.

 

 

 

 

 

 

그래서 문제를 다시한번 분석해보았다.

 

핵심은 중복된 수가 나열되는 경우 중복된 조합을 만든다는것이었다.

 

가령 ... 2, 2, 2, 2.... 라는 구간이 나온다면

 

저기서 중복된 조합이 만들어지지 않도록 방지해야 하는것이다.

 

즉 우리가 신경쓸것은 2를 몇번 더하느냐인것이다.

 

즉 2가 연속된 구간에 대해선

 

0,2,4,6,8

 

5개를 더하는 분기점만 형성하면 된다.

 

그렇기에

 

배열을 정열한 후 한곳에 뭉처있는 수가 무엇이며, 몇개인지를 nums와 cnts 배열에 넣어서 완전탐색을 진행하면 된다.

 

 

class Solution {
public:
    vector<vector<int>> ans;
 
    int N;
    int nums[100];
    int cnts[100];
    int goal;
 
    void DFS(int arrSize, int sum) {
        if (sum == goal) {
            ans.push_back(ans[ans.size() - 1]);
            return;
        }
 
        if (sum > goal)
            return;
 
        if (arrSize == N)
            return;
        
        int num =0;
        for (int i = 0; i <= cnts[arrSize]; i++) {
            if(sum + (i * nums[arrSize]) > goal)
                break;
            
            DFS(arrSize + 1, sum + (i * nums[arrSize]));
            ans[ans.size() - 1].push_back(nums[arrSize]);
            num++;
        }
 
        //ans[ans.size() - 1].erase(ans[ans.size() - 1].end() - (cnts[arrSize] + 1), ans[ans.size() - 1].end());
        
        
        for (int i = 0; i < num; i++)
            ans[ans.size() - 1].pop_back();
        
    }
 
 
    vector<vector<int>> combinationSum2(vector<int>& v, int tar) {
        N = v.size();
        goal = tar;
        sort(v.begin(), v.end());
        int cnt = 0, prevNum = v[0], index = 0;
        for (int i = 0; i < N; i++) {
            if (prevNum == v[i]) {
                cnt++;
            }
            else {
                nums[index] = prevNum;
                cnts[index] = cnt;
 
                prevNum = v[i];
                cnt = 1;
                index++;
            }
        }
 
        nums[index] = prevNum;
        cnts[index] = cnt;
        index++;
 
        N = index;
        /*
        for(int i=0; i<index; i++)
            cout << nums[i] << " ";
 
        cout << endl;
 
        for(int i=0; i<index; i++)
            cout << cnts[i] << " ";
        */
        ans.push_back(vector<int>());
        DFS(0, 0);
        ans.pop_back();
 
        return ans;
    }
};
 

 

 

16ms에 45%라는 조금 개선된 성능을 보였지만 여전히 아쉬운 성능이다.

 

완전 탐색을 돌리기위한 기반코드로

2piN (N : cnts와 nums 배열의 길이)

 

를 기반으로하여 해당 숫자를 포함할지 말지를 결정하는 방법으로 분기를 형성했다.

 

하지만 선택하지 않는 경우에도 추가적인 분기점을 형성할 필요는 없기에

 

아래의 방법으로 개선했다.

 

 

class Solution {
public:
    vector<vector<int>> ans;
 
    int N;
    int nums[100];
    int cnts[100];
    int goal;
 
    void DFS(int arrSize, int sum) {       
 
        if (sum == goal) {
            ans.push_back(ans[ans.size() - 1]);
            return;
        }
 
        if (sum > goal)
            return;
 
        if (arrSize == N)
            return;
 
        bool isEnd = false;
        int newCnt = 0;
        for (int i = arrSize; i < N; i++) {
 
            if (sum + nums[i] > goal)
                break;
 
            newCnt = 0;
 
            for (int j = 1; j <= cnts[i]; j++) {
                if (sum + (j * nums[i]) > goal) {
                    break;
                }
 
                ans[ans.size() - 1].push_back(nums[i]);
                DFS(i + 1, sum + (j * nums[i]));
                newCnt++;
            }
 
 
            for (int j = 0; j < newCnt; j++)
                ans[ans.size() - 1].pop_back();                        
        }
    }
 
 
    vector<vector<int>> combinationSum2(vector<int>& v, int tar) {
        N = v.size();
        goal = tar;
        sort(v.begin(), v.end());
        int cnt = 0, prevNum = v[0], index = 0;
        for (int i = 0; i < N; i++) {
            if (prevNum == v[i]) {
                cnt++;
            }
            else {
                nums[index] = prevNum;
                cnts[index] = cnt;
 
                prevNum = v[i];
                cnt = 1;
                index++;
            }
        }
 
        nums[index] = prevNum;
        cnts[index] = cnt;
        index++;
 
        N = index;
        /*
        for(int i=0; i<index; i++)
            cout << nums[i] << " ";
 
        cout << endl;
 
        for(int i=0; i<index; i++)
            cout << cnts[i] << " ";
        */
        ans.push_back(vector<int>());
        DFS(0, 0);
        ans.pop_back();
 
        return ans;
    }
};
 

 

4ms에 98.84% 라는 만족스러운 성능이 나왔다.

 

상수 처리를 잘한다면 0ms도 가능할듯하다

 

 

2piN의 완전탐색을 할경우엔 내부적으로 반복문을 통해 분기점을 줄일 방법이 있음을 명심할것