子集 + 子集 II AND 零花钱兑换 + 零钱兑换 II

78. 子集

方法一 枚举

假设有n个数字，每个数字有出现(1)和不出现(0)两种情况，那么用0和1来表示其子集二进制就是000...000 ~111...111，即0~2^n-1，一共2^n种情况。于是遍历当出现1的时候加入当前表示的子集即可。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        for(int mask = 0; mask < (1 <<n);mask++){
            vector<int> cur;
            for(int j =0; j < n ;j++){
                if(mask &(1<<j)){
                    cur.push_back(nums[j]);
                }
            }
            res.push_back(cur);
        }
        return res;

    }
};

image.png

方法二 递归

class Solution {
public:
    vector<vector<int>> res;
    vector<int> t;
    int n,i=0 ;
    void dfs(vector<int>& nums,int cur){
        if(cur == n){
            res.push_back(t);
            return ;
        }
        t.push_back(nums[cur]);
        dfs(nums,cur+1);//选择cur这一位
        t.pop_back();
        dfs(nums,cur+1);//没有选这一位
    }
    vector<vector<int>> subsets(vector<int>& nums) {          
        n = nums.size();
        dfs(nums,0);
        return res;
    }
};

90. 子集 II

这道题跟上题不同之处在于，可能包含重复元素。

方法一 递归

在递归时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    int n;
    set<vector<int>> s;
    void dfs(bool choosePre,vector<int>& nums, int cur){
        if(cur == n){
            if(!s.count(temp)){
                res.push_back(temp); 
                s.insert(temp);   
            }
            
            return ;
        }
        dfs(false,nums,cur+1);
        if(!choosePre&& cur >0&&nums[cur-1] == nums[cur]) return;
        temp.push_back(nums[cur]);
        dfs(true,nums,cur+1);
        temp.pop_back();
      
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        n = nums.size();
        sort(nums.begin(),nums.end());
        dfs(false,nums,0);
        return res;
    }
};

image.png

方法二 枚举

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
       vector<vector<int>> res;
        int n = nums.size();
        sort(nums.begin(),nums.end());
       
        for(int mask = 0; mask < (1 <<n);mask++){
            vector<int> cur;
             bool flag = true;
            for(int j =0; j < n ;j++){
                if(mask &(1<<j)){
                    if (j > 0 && (mask >> (j - 1) & 1) == 0 && nums[j] == nums[j - 1]) {
                        flag = false;
                        break;
                    }
                    cur.push_back(nums[j]);
                }
            }
            if(flag){
                res.push_back(cur);
            }
        }
        return res;
    }
};

image.png

扩展

39.组合总和

40. 组合总和 II

46. 全排列

47. 全排列 II

78. 子集

90. 子集 II

322. 零钱兑换

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        m = len(coins)

        dp = [0 for i in range(amount+1)]
        dp[0] = 1
        for i in range(m):
            for j in range(amount, -1, -1):
                if(i == 0 and j % coins[i] == 0):
                    dp[j] = 1
                    continue
                if(j-coins[i]>=0):
                    dp[j] += dp[j-coins[i]]
        return dp[amount]

518. 零钱兑换 II

与零钱兑换不同的是需要考虑重复计算的情况

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int& coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

image.png