Summarize for all permutation and combination problems
Description
To do list
- Permutations
- Unique Permutations
- Combination Sum
- Letter Combination of a Phone Number
- Palindrome Partitioning
- Restore IP Address
Problem Set
Subsets
Subsets I
DescriptionSolutionNote
Given a set of distinct integers, return all possible subsets.
Notice:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution: """ @param S: The set of numbers. @return: A list of lists. See example. """ def subsets(self, S): if not S: return None ans = [] self.search(ans, [], sorted(S), 0) return ans def search(self, ans, clist, nums, pos): ans.append(clist) for i in range(pos, len(nums)): self.search(ans, clist + [nums[i]], nums, i+1) |
|
1 2 3 4 5 6 7 8 9 |
# Another version for search() # in this version, make a copy of clist at the begining, and modify it for next node # in previous version, make a copy of clist when invoke search() for each next node def search(self, ans, clist, nums, pos): ans.append(list(clist)) for i in range(pos, len(nums)): clist.append(nums[i]) self.search(ans, clist, nums, i+1) clist(-1) |
Subsets II
DescriptionSolutionNote
Given a list of numbers that may has duplicate numbers, return all possible subsets.
Notice:
- Each element in a subset must be in non-descending order.
- The ordering between two subsets is free.
- The solution set must not contain duplicate subsets.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution: """ @param S: A set of numbers. @return: A list of lists. All valid subsets. """ def subsetsWithDup(self, S): if not S: return None ans = [] self.search(ans, [], sorted(S), 0) return ans def search(self, ans, clist, nums, pos): ans.append(clist) for i in range(pos, len(nums)): if i != pos and nums[i] == nums[i-1]: continue self.search(ans, clist + [nums[i]], nums, i+1) |
Permutations
Permutation I
DescriptionSolutionNote
Given a list of numbers, return all possible permutations.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution: """ @param nums: A list of Integers. @return: A list of permutations. """ def permute(self, nums): if not nums: return [] ans = [] self.search(ans, [], sorted(nums)) return ans def search(self, ans, clist, nums): if len(clist) == len(nums): ans.append(clist) for item in nums: if item in clist: continue self.search(ans, clist + [item], nums) |
Permutation II
DescriptionSolutionNote
Given a list of numbers with duplicate number in it. Find all unique permutations.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution: """ @param nums: A list of integers. @return: A list of unique permutations. """ def permuteUnique(self, nums): if not nums: return [] ans = [] visited = [0]*len(nums) self.search(ans, [], visited, sorted(nums)) return ans def search(self, ans, clist, visited, nums): if len(clist) == len(nums): ans.append(clist) for i in range(len(nums)): if visited[i] or (i != 0 and nums[i] == nums[i-1] and visited[i-1] == 0): continue visited[i] = 1 self.search(ans, clist + [nums[i]], visited, nums) visited[i] = 0 |
Submit a Comment