runtime 0 ms, beats 100% of cpp submissions
O(2^n) solution with explanation

tags: backtracking

Combination Sum II

๐Ÿ“– description

็ตฆๅฎšไธ€ๅ€‹้™ฃๅˆ— candidates ๏ผŒ่ˆ‡้œ€่ฆ็ต„ๅˆ็š„ target ๏ผŒ่ซ‹ๆฑ‚ๆ‰€ๆœ‰ๅฏ่ƒฝ็š„็ต„ๅˆๆ–นๅผใ€‚

ex.
    Input: candidates = [10,1,2,7,6,1,5], target = 8

    Output: 
        [
        [1,1,6],
        [1,2,5],
        [1,7],
        [2,6]
        ]

๐Ÿง  solution

Combination Sum
Combination Sum solution
Combination Sum ้กŒ็›ฎ็š„้€ฒๅŒ–็‰ˆ๏ผŒๆฏๅ€‹ๅ…ƒ็ด ๅ–ฎๆฌกๆ‹ฟๅ–๏ผŒไธ”่ฆๆฑ‚็ต„ๅˆไธ่ƒฝ้‡่ค‡ใ€‚

้‡ๅฐ็”Ÿๆˆๅฏ่ƒฝ็ต„ๅˆ็š„ๆ–นๅผ๏ผŒไธฆๆฒ’ๆœ‰ๅคชๅคš็š„่ฎŠๅŒ–๏ผŒ้œ€่ฆ่™•็†็š„้ƒจๅˆ†ๆ˜ฏ็ต„ๅˆไธ่ƒฝ้‡่ค‡๏ผŒๆœ‰ไปฅไธ‹ๅ…ฉๅ€‹ๆ–นๆณ•

  • ไฝฟ็”จ set ๅŽป้‡ (็„กๆณ•ไฝฟ็”จ hashset ๏ผŒๅ› ็‚บ c++ ไธๆ”ฏๆด hashset ้‡ๅฐ vector ็š„็ดขๅผ•)
  • sort candidates ๅœจ็ต„ๅˆ็š„้Ž็จ‹ไธญๅˆคๆ–ทไธฆ้ฟๅ…้‡่ค‡็ต„ๅˆใ€‚

็ฌฌไธ€็จฎๆ–นๆณ•ๅฏฆไฝœ้žๅธธ็ฐกๅ–ฎ๏ผŒไฝ†ๆ˜ฏๆœ‰ๅ…ฉๅ€‹็ผบ้ปž

  • ้œ€่ฆไฝฟ็”จ้กๅค–็ฉบ้–“
  • ๆœƒ้€ฒๅ…ฅ้‡่ค‡็š„็ต„ๅˆไธญ๏ผŒๅขžๅŠ ่จˆ็ฎ—้‡

่€Œ็ฌฌไบŒ็จฎๆ–นๆณ•ๅ‰‡้œ€่ฆ sort candidates ๏ผŒ่จˆ็ฎ—้‡็›ธๅฐ่ผƒๅฐ

โณ time complexity

ๅฐ candidates ๆŽ’ๅบ๏ผŒๆ™‚้–“่ค‡้›œๅบฆ O(nlog(n))
ๅ›žๆœ”ๅฐ‹ๆ‰พๅฏ่ƒฝ็ต„ๅˆ๏ผŒๆฏๅ€‹ๅ…ƒ็ด ๅฏ่ƒฝๆ‹ฟๅฏ่ƒฝไธๆ‹ฟ๏ผŒๆ™‚้–“่ค‡้›œๅบฆ O(2^n)
็ธฝๆ™‚้–“่ค‡้›œๅบฆ O(2^n)

๐Ÿ“ code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void re(vector<int>& c,vector<int>& now,vector<vector<int>>& ans,int ind,int r){
        if(r==0){
            ans.emplace_back(now);
        }
        else if(ind>=c.size() || r<0){
            return;
        }
        else{
            for(int i=ind;i<c.size() && c[i]<=r;i++){
                if(i==ind || c[i-1]!=c[i]){     // ๆญ้… sort ๅŽป้™ค้‡่ค‡็‹€ๆ…‹
                    now.emplace_back(c[i]);
                    re(c,now,ans,i+1,r-c[i]);
                    now.pop_back();
                }
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& c, int t) {
        sort(c.begin(),c.end());
        vector<int> now;
        vector<vector<int>> ans;
        re(c,now,ans,0,t);
        return ans;
    }
};