Given a set of distinct integers, return all possible subsets.
http://www.lintcode.com/en/problem/subsets/
Notice
Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.
Example If S = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
In [7]:
class Solution:
"""
@param S: The set of numbers.
@return: A list of lists. See example.
"""
def subsets(self, S):
# write your code here
self.ans = []
S.sort()
self.search(S, [], 0)
return self.ans
def search(self, S, subset, index):
if index == len(S):
self.ans.append(subset)
return
self.search(S, subset + [S[index]], index + 1)
self.search(S, subset, index + 1)
Given a list of numbers, return all possible permutations.
http://www.lintcode.com/en/problem/permutations/
https://leetcode.com/problems/permutations/#/description
You can assume that there is no duplicate numbers in the list.
Example For nums = [1,2,3], the permutations are:
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
In [10]:
class Solution:
"""
@param nums: A list of Integers.
@return: A list of permutations.
"""
def permute(self, nums):
# write your code here
if nums is None:
return []
if len(nums) == 0:
return [[]]
def helper(ans, temp, nums):
if len(nums) == 0:
ans += [temp]
else:
for i in range(len(nums)):
helper(ans, temp + [nums[i]], nums[:i] + nums[i+1:])
ans = []
helper(ans, [], sorted(nums))
return ans
In [8]:
nums = [1,2,3]
i = 2
nums[i+1:]
Out[8]:
In [ ]: