組合、排列、子集 - a920604a/leetcode GitHub Wiki

title: 組合、排列、子集 tags:
- backtracking categories: - CS - Algorithm comments: false

題目

  • 46 Permutations

  • 47 Permutations II

  • 31 Next Permutation

  • 784 Letter Case Permutation

  • 78 Subsets

  • 90 Subsets II

  • 2597 The Number of Beautiful Subsets

  • 77 Combinations

  • 39 Combination Sum

  • 40 Combination Sum II

  • 216 Combination Sum III

觀念

組合與排列最大差異，排列是有順序，組合沒有順序，所以排列數通常較大

  • 排列，每個元素都必須包含，所以每次都需要重頭拜訪，需要額外vector used來紀錄該元素是否拜訪過。當然也可迴圈遍歷find()檢查其值是否已包含，但較費時且也較不泛化。

  • 組合沒有順序性可言，不必重頭拜訪，所以可以事先用排序，在借助vector used 或 if(i > s && nums[i] == nums[i-1]) continue; 條件語句。

  • 子集，沒有順序性可言，不必重頭拜訪。紀錄拜訪樹的每個路徑，不拜訪錯過的

  • 陣列有重複元素，可以排序，搭配if(i > s && nums[i] == nums[i-1]) continue;，去掉重複元素，或是vector used，去掉重複元素

  • 78 Subsets

  • 90 Subsets II

  • 784 Letter Case Permutation

DFS

77 Combinations

void traverse(int l, int r, int k, vector<int> &path, vector<vector<int>> &ret){
        
        if(path.size() == k){
            ret.push_back(path);
            return;
        }       
        for(int i=l;i<=r;++i){
            path.push_back(i);
            traverse(i+1, r, k, path, ret);
            path.pop_back();
        }
        
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        vector<int> path;
        traverse(1, n, k, path, ret);
        return ret;
    }

39 Combination Sum

void traverse(int s, vector<int> &candidates, int target, vector<vector<int>>&ret, vector<int> &path){
        // base case
        if(target <0) return;
        if(target == 0){
            ret.push_back(path);
            return;
        }
        for(int i=s;i<candidates.size() ;++i){
            
            path.push_back(candidates[i]);
            traverse(i, candidates, target - candidates[i], ret, path);
            path.pop_back();
        }        
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> path;
        traverse(0, candidates, target, ret, path);
        return ret;        
    }

40 Combination Sum II

vector<vector<int>> ret;
void traverse(vector<int>& candidates, int target, int l, int r, vector<int>&path){
    if(target<0) return;
    if(target==0){
        ret.push_back(path);
    }
    for(int i=l;i<=r ;++i){
        if (i == l || candidates[i] != candidates[i - 1]){
            path.push_back(candidates[i]);
            traverse(candidates, target-candidates[i], i+1,r, path);
            path.pop_back();
        }
    }
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<int> path;
    traverse(candidates, target, 0,candidates.size()-1 , path);
    return ret;
}

216 Combination Sum III

vector<vector<int>> ret;
void traverse(int start, int k, int target, vector<int> &path ){
    if(target<0) return;
    if(target==0) {
        if(path.size() == k) ret.push_back(path);
        return;
    }
    
    for(int i=start ;i<=9;++i){
        // if(cur + i > n) break; 
        path.push_back(i);
        traverse(i+1, k, target-i, path);
        path.pop_back();
    }
}
vector<vector<int>> combinationSum3(int k, int n) {
    vector<int> path;
    traverse(1, k, n, path);
    return ret;

Permutations

46 Permutations

vector<vector<int>> ret;
void traverse(vector<int>& nums, vector<int>& path){
    if(path.size() == nums.size()){
        ret.push_back(path);
        return;
    }
    
    for(int i=0;i<nums.size();  ++i){
        if(find(path.begin(), path.end(), nums[i])!=path.end()) continue;
        path.push_back(nums[i]);
        traverse(nums, path);
        path.pop_back();
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    vector<int> path;
    traverse(nums, path);
    return ret;        
}

47 Permutations II

set<vector<int>> ret;
void traverse(vector<int> & nums, vector<int> &path, vector<bool> & visited){
    
    if(path.size() == nums.size()){
        // ret.push_back(path);
        ret.insert(path);
        return;
    }
    for(int i=0; i<nums.size() ;++i){
        if(visited[i]) continue;
        visited[i] = true;
        path.push_back(nums[i]);
        traverse(nums, path, visited);
        visited[i] = false;
        path.pop_back();
    }
    
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<int> path;
    vector<bool> visited(nums.size(), false);
    traverse(nums, path, visited);
    return vector<vector<int>>(ret.begin(), ret.end());
    
}

31 Next Permutation

void nextPermutation(vector<int>& nums) {
        
    int n = nums.size();
    int k;
    for(k = n-2;k>-1 ;k--){
        if(nums[k]<nums[k+1]) break;
    }
    
    if(k<0){
        reverse(nums.begin(), nums.end());
    }
    else{
        
        int j ;
        for(j = n-1;j>k;j--){
            if(nums[j]> nums[k]) break;
        }
        
        swap(nums[j], nums[k]);
        reverse(nums.begin() + k+1, nums.end());
    }
}

784 Letter Case Permutation

vector<string> ret;
    void traverse(string &s, string &path, int l){
        
        if(path.size() == s.size()){
            ret.push_back(path);
        }
        // if(l>= s.size()) reutrn;
        
        for(int i=l;i<s.size();++i){
            // 因為只會有大小寫與數字
            if(s[i] >='0' && s[i]<='9'){
                path.push_back(s[i]);
                traverse(s, path, i+1);
                path.pop_back();
                
            }
            // if(( s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z')){
            else{
                // 選擇小寫
                path.push_back(tolower(s[i]));
                traverse(s, path, i+1);
                path.pop_back();
                
                // 選擇大寫
                path.push_back(toupper(s[i]));
                traverse(s, path, i+1);
                path.pop_back();
            }        
        }
    }
    vector<string> letterCasePermutation(string s) {
        string path;
        traverse(s, path, 0);
        return ret;        
        
    }

Subsets

78 Subsets

vector<vector<int>> ret;
void traverse(vector<int> &nums, vector<int>&path, int l){
    
    ret.push_back(path);
    // if(l>=nums.size()) return;
    
    for(int i=l;i<nums.size();++i){
        path.push_back(nums[i]);
        traverse(nums, path, i+1);
        path.pop_back();
    }
    
}
vector<vector<int>> subsets(vector<int>& nums) {
    
    vector<int> path;
    traverse(nums, path, 0);
    return ret;
}

90 Subsets II

vector<vector<int>> ret;
void traverse(vector<int> &nums, vector<int>&path, int l){

    ret.push_back(path);
    
    for(int i=l;i<nums.size();++i){
        if(i>l || nums[i-1]!=nums[i]){
            path.push_back(nums[i]);
            traverse(nums, path, i+1);
            path.pop_back();
        }
    }
    
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> path;
    traverse(nums, path, 0);
    return ret;
    
}

Combinations

77. Combinations

class Solution {
public:
    vector<vector<int>> ret;
    void traverse(int n, int k, vector<int> & path, int start){
        // 終止條件
        if(path.size() ==k){
            ret.push_back(path);
            return;
        }
        
        for(int i=start;i<=n;++i){
            path.push_back(i);
            // [2,4] OK , [4,2] not OK -> 只允許遞增，避免重複
            traverse(n,k,path, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        traverse(n,k,path, 1);
        return ret;
    }
};

39. Combination Sum

class Solution {
public:
    vector<vector<int>> ret;
    void traverse(vector<int>& candidates, int target, vector<int>& path, int s){
        // 終止條件
        if(target<0) return;
        if(target==0){
            ret.push_back(path);
            return;
        }
        
        for(int i=s;i<candidates.size();++i){
            // option
            if(target < candidates[i]) return;
            
            path.push_back(candidates[i]);
            // 因為可重複拿取同一元素
            traverse(candidates, target-candidates[i], path, i);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        traverse(candidates, target, path, 0);
        return ret;
        
    }
};

40. Combination Sum II

class Solution {
public:
    vector<vector<int>> ret;
    void traverse(vector<int>& candidates, int target, vector<int> & path, int j){
        if(target<0 ) return;
        
        if(target==0){ret.push_back(path); return;}
        
        for(int i=j;i<candidates.size();++i){
            if(i>j && candidates[i-1] == candidates[i]) continue;
            path.push_back(candidates[i]);
            traverse(candidates, target-candidates[i], path, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        
        vector<int> path;
        traverse(candidates, target, path, 0);
        return ret;
    }
};

216. Combination Sum III

class Solution {
public:
    vector<vector<int>> ret;
    void traverse(int k, int n, int j, vector<int>& path){
        
        if(k == path.size()){
            if(n==0) ret.push_back(path);
            return;
        }
        for(int i = j;i<=9;++i){
            path.push_back(i);
            traverse(k, n-i, i+1, path);
            path.pop_back();
        }
        
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        
        vector<int> path;
        traverse(k, n, 1, path);
        return ret;
    }
};

License

footer

⚠️ **GitHub.com Fallback** ⚠️