C++ 回溯算法
参见leetcode用户Tom也要Offer 分享的题解
https://leetcode.cn/problems/subsets/solutions/229569/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/
class Solution
{
public:
vector<vector<int>> subsets(vector<int>& nums)
{
vector<vector<int>> res;
vector<int> path;
backtrack(nums, res, path, 0 );
return res;
}
void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<int>& path, int start)
{ //回溯算法
res.push_back(path); //此题全部分支都符合,无需额外的判断条件
for(int i=start; i < nums.size(); i++)
{
path.push_back(nums[i]);//做出选择
backtrack(nums, res, path, i+1);//递归进入下一层,注意i+1,标识下一个选择列表的开始位置,最重要的一步
path.pop_back();//撤销选择
}
}
};
C++ 二进制数迭代法 (参见本题的官方题解)
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};
Python 动态规划
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for i in range(len(nums)):
path = []
for r in res:
path.append(r + [nums[i]])
res.extend(path)
return re
果然是人生苦短......
本文分享自 Python可视化编程机器学习OpenCV 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!