Subsets
https://leetcode.com/problems/subsets/
思路1
这里其实就是把Combination拿到题目的思路2，收集那种组合树所有root到其余节点（不包括root本身）path。
class Solution:
# @param S, a list of integer
# @return a list of lists of integer
def subsets(self, S):
def dfs(depth, start, valuelist):
res.append(valuelist)#回溯的时候 每一层都要记录为结果就行
if depth == len(S): return
for i in range(start, len(S)):
dfs(depth+1, i+1, valuelist+[S[i]])#这里注意是使用的+一个list，即valuelist并没有被传入递归函数中，所以当这个函数返回之后，valuelist并没有变。例如，递归完左子树返回之后，valuelist依然还是递归左子树之前的值。这里传入的是合并的list，属于一个新list
#所以这里其实是用python语言的特点，使得在模板中提到的改变变量->递归所有子节点->恢复变量的过程简化了
S.sort()
res = []
dfs(0, 0, [])
return res思路2
类似与combination. 利用backtracking的模板
class Solution(object):
def dfs(self, m, nums, subres, res):
if m >= len(nums):
tmp = [nums[i] for i,c in enumerate(subres) if c == 1]
tmp.sort()
res.append(tmp)
return
else:
subres[m] = 0
self.dfs(m+1, nums, subres, res)
subres[m] = 1
self.dfs(m+1, nums, subres, res)
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
subres = [0]*len(nums)
res = []
self.dfs(0, nums, subres, res)
return res思路2
还可以用bitmap的办法做
http://algorithm.yuanbin.me/zh-cn/exhaustive_search/subsets.html
自己重写code
class Solution(object):
def dfs(self, candidates, start, end, subres, res):
res.append(subres)
for i in xrange(start, end):
self.dfs(candidates, i + 1, end, subres + [candidates[i]], res)
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
self.dfs(nums, 0, len(nums), [], res)
return resSubsets II
https://leetcode.com/problems/subsets-ii/
思路1
class Solution:
# @param num, a list of integer
# @return a list of lists of integer
def subsetsWithDup(self, S):
def dfs(depth, start, valuelist):
if valuelist not in res: res.append(valuelist)
if depth == len(S): return
for i in range(start, len(S)):
dfs(depth+1, i+1, valuelist+[S[i]])
S.sort()
res = []
dfs(0, 0, [])
return res思路2
加上一个判断重复的条件即可
class Solution(object):
def dfs(self, m, nums, subres, res):
if m >= len(nums):
tmp = [nums[i] for i,c in enumerate(subres) if c == 1]
tmp.sort()
if tmp not in res:#加上这个条件即可
res.append(tmp)
return
else:
subres[m] = 0
self.dfs(m+1, nums, subres, res)
subres[m] = 1
self.dfs(m+1, nums, subres, res)
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
subres = [0]*len(nums)
res = []
self.dfs(0, nums, subres, res)
return res自己重写code
class Solution(object):
def dfs(self, candidates, start, end, subres, res):
if subres not in res: res.append(subres)
for i in xrange(start, end):
self.dfs(candidates, i + 1, end, subres + [candidates[i]], res)
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
self.dfs(nums, 0, len(nums), [], res)
return res