【LeetCode with Python】 78. Subsets
题目
原题页面:https://leetcode.com/problems/subsets/
本文地址:http://leetcode.xnerv.wang/subsets/
题目类型:Array, Backtracking, Bit Manipulation
难度评价:Medium
Given a set of distinct integers, nums, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If nums =[1,2,3]
, a solution is:
[][3],<br/> [1],<br/> [2],<br/> [1,2,3],<br/> [1,3],<br/> [2,3],<br/> [1,2],<br/> []<br/>
分析
普通的搜索算法即可解决,不过注意每个子序列都要以升序排列,所以从一开始就把输入的S排好序,一了百了,不知道是否还有其它更好的算法。
递归回溯的两个关键:递和归。递即分支条件,在本题里指的是是否选择某个元素,而形成每次的两个分支。归即结束条件,在本题里指已经考察完全部元素。
代码
class Solution:
def __init__(self):
self.results = [ ]
def doSubsets(self, S, cur_list, cur_index):
if cur_index > len(S) - 1:
self.results.append(cur_list)
return
cur_list0 = cur_list[:]
cur_list1 = cur_list[:]
cur_list1.append(S[cur_index])
self.doSubsets(S, cur_list0, cur_index + 1)
self.doSubsets(S, cur_list1, cur_index + 1)
# @param S, a list of integer
# @return a list of lists of integer
def subsets(self, S):
S.sort()
self.doSubsets(S, [ ], 0)
return self.results