Combinatorics¶
Table of Contents
Backtracking¶
Permutation, Combinations, Paranthesis, Subsets
Expand Code
1def permute(self, nums: List[int]) -> List[List[int]]: 2 def backtrack(index, n): 3 nonlocal res 4 if index == n: 5 res.append(nums[:]) 6 return 7 for i in range(index, n): 8 nums[i], nums[index] = nums[index], nums[i] 9 backtrack(index + 1, n) 10 nums[i], nums[index] = nums[index], nums[i] 11 res = [] 12 backtrack(0, len(nums)) 13 return res 14 15def combine(self, n: int, k: int) -> List[List[int]]: 16 def optimized(): 17 """ prevents wasteful subset formation with additional state information """ 18 # [1,2,3] curr start range 19 # remaining=2, [] 1-> [1,2] 20 # remaining=1, [1], [2] 2-> [2,3], 3 -> [3] 21 # remaining=0, [1,2],[1,3],[2,3] 22 def backtrack(curr, start): 23 nonlocal res 24 remaining = k - len(curr) 25 if not remaining: 26 res.append(curr[:]) 27 return 28 for num in range(start, n - remaining + 2): 29 curr.append(num) 30 backtrack(curr, num + 1) 31 curr.pop() 32 res = [] 33 backtrack([], 1) 34 return res 35 """ 36 with indices 37 def backtrack(curr, start_index): 38 nonlocal nums, res 39 remaining = k - len(curr) 40 if not remaining: 41 res.append(curr[:]) 42 return 43 for index in range(start_index, len(nums) - remaining + 1): 44 curr.append(nums[index]) 45 backtrack(curr, index + 1) 46 curr.pop() 47 res = [] 48 nums = list(range(1, n+1)) 49 backtrack([], 0) 50 return res 51 """ 52 53 def simple(): 54 """ In this formulation, subsets get wasted, e.g. [3] """ 55 # [1,2,3] start range 56 # k=0, [] 1-> [1,2,3] 57 # k=1, [1], [2], [3] 2-> [2,3], 3->[3] 58 # k=2, [1,2],[1,3],[2,3] 59 def backtrack(curr, start): 60 nonlocal res 61 if len(curr) == k: 62 res.append(curr[:]) 63 return 64 for num in range(start, n + 1): 65 curr.append(num) 66 """ NOTE: NOT START + 1""" 67 backtrack(curr, num + 1) 68 curr.pop() 69 res = [] 70 backtrack([], 1) 71 return res 72 73def generateParenthesis(self, n: int) -> List[str]: 74 # n = 3 left right 75 # ( 1 0 76 # ((, () 1 1 77 # (((,((), ()( 2 1 78 # (((,(()(,()((,()() 79 """ 80 key idea: 81 (1) when to add ( => whenever there are still left paranthesis left to add 82 (2) when to add ) => whenever left count is greater than right count 83 """ 84 def backtrack(curr, left_count, right_count): 85 nonlocal res 86 if right_count == n: 87 res.append(''.join(curr)) 88 return 89 # add ( if applicable 90 if left_count < n: 91 curr.append('(') 92 backtrack(curr, left_count + 1, right_count) 93 curr.pop() 94 # add ) if applicable 95 if right_count < left_count: 96 curr.append(')') 97 backtrack(curr, left_count, right_count + 1) 98 curr.pop() 99 res = [] 100 backtrack([], 0, 0) 101 return res 102 103def subsets(self, nums: List[int]) -> List[List[int]]: 104 def choice(): 105 """ Best approach """ 106 # $: [] 107 # 1: [],[1] 108 # 2: [],[1],[2],[1,2] 109 # 3: [],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3] 110 def backtrack(curr, index): 111 nonlocal res 112 if index == len(nums): 113 res.append(curr[:]) 114 return 115 # leave it 116 backtrack(curr, index + 1) 117 # take it 118 curr.append(nums[index]) 119 backtrack(curr, index + 1) 120 curr.pop() 121 122 res = [] 123 backtrack([], 0) 124 return res 125 126 def forward(): 127 # [] 128 # [],[1] 129 # [],[1],[2],[1,2] 130 # [],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3] 131 def backtrack(curr, index): 132 if index == len(nums): 133 return curr 134 prev = copy.deepcopy(curr) 135 for ans in curr: 136 ans.append(nums[index]) 137 return backtrack(prev + curr, index + 1) 138 return backtrack([[]], 0) 139 140 def backward(): 141 # [1,2,3] 142 # [] 143 # [3],[] 144 # [2,3],[2],[3],[] 145 # [1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[] 146 def backtrack(index): 147 if index == len(nums): 148 return [[]] 149 res = backtrack(index + 1) 150 n = len(res) 151 for i in range(n): 152 curr = copy.deepcopy(res[i]) 153 curr.append(nums[index]) 154 res.append(curr) 155 return res 156 return backtrack(0)