→ JIWP: 別卷了 05/21 12:16
推 SecondRun: 大師 05/21 12:22
※ 引述《ray90514 ()》之銘言：
: 78. Subsets
: 基本上跟昨天一樣 不過這次試著寫一個非遞迴的
: class Solution {
: public:
: vector<vector<int>> subsets(vector<int>& nums) {
: vector<vector<int>> ans;
: ans.push_back(vector<int>());
: for(int n : nums){
: int len = ans.size();
: for(int i = 0; i < len; i++){
: vector<int> v = ans[i];
: v.push_back(n);
: ans.push_back(v);
: }
: }
: return ans;
: }
: };
思路:
backtracking
Python Code:
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(state,nums,start,res):
if state not in res:
res.append(list(state))
for i in range(start,len(nums)):
state.append(nums[i])
backtrack(state,nums,i+1,res)
state.pop()
res=[[]]
backtrack([],nums,0,res)
return res
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.130.118 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716264967.A.21A.html