正文
leetcode78
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
本题是回溯法的基本应用，深度优先遍历，使用递归实现。
class Solution {
public:
int x[];
vector<vector<int>> R;
int n;
//t当前查询的位置
void BackTrack(vector<int> nums, int t)
{
if (t >= n)//达到叶子节点
{
vector<int> V;
for (int i = ; i < n; i++)
{
if (x[i] == )
{
V.push_back(nums[i]);
}
}
R.push_back(V);
return;
}
x[t] = ;
BackTrack(nums, t + );
x[t] = ;
BackTrack(nums, t + );
}
vector<vector<int>> subsets(vector<int>& nums) {
n = nums.size();
memset(x, , sizeof(x));
BackTrack(nums, );
return R;
}
};
补充一个python版本：
class Solution:
def __init__(self):
self.L = list()
self.N = 0 def backTrack(self,nums,index,l):
if index >= self.N:
self.L.append(l[:])
return
l.append(nums[index])
self.backTrack(nums,index+1,l) l.pop(-1)
self.backTrack(nums,index+1,l) def subsets(self, nums: 'List[int]') -> 'List[List[int]]':
self.N = len(nums)
l = list()
self.backTrack(nums,0,l)
return self.L
