Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
consideration of permutations.
'''
link
- https://leetcode.com/problems/permutations/
problem:
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
'''
# solution 1
def dfs1(nums, path, ans):
if len(nums) == 0:
ans.append(path)
for i in range(len(nums)):
dfs1(nums[:i]+nums[i+1:], path+[nums[i]], ans)
def main1():
result = []
nums = [1, 2, 3]
dfs1(nums, [], result)
print(result)
if __name__ == '__main__':
main1()
# solution 2
def dfs2(nums):
ans = []
if len(nums) == 1:
return [[]]
for i in range(len(nums)):
for sub in dfs2(nums[:i]+nums[i+1:]):
ans.append(sub+[nums[i]])
return ans
def main2():
nums = [1, 2, 3]
result = dfs2(nums)
print(result)
if __name__ == '__main__':
main2()
'''
link
- https://leetcode.com/problems/subsets/
problem:
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
'''
# solution A
def dfsA(nums, sets):
if len(nums) == 0:
return
e = nums.pop()
subsets = list(sets)
for s in subsets:
sets.append(s+[e])
dfsA(nums, sets)
def mainA():
result = [[]]
nums = [1, 2, 3]
dfsA(nums, result)
print(result)
if __name__ == '__main__':
mainA()
# solution B
def dfsB(nums):
ans = []
if len(nums) == 1:
return [nums]
e = nums.pop()
ans.append([e])
for sub in dfsB(nums):
ans.extend([sub, [e]+sub])
return ans
def mainB():
nums = [1, 2, 3]
result = dfsB(nums) + [[]]
print(result)
if __name__ == '__main__':
mainB()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.