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
扩展
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
