# **程式筆記(recursion)**
:::info
:information_source: 日期 : 2023/07/10
:::
**:thumbsup:** 總結
1. sorted(list)
功用
subset不會重複
例如給定[1, 2, 2]時，不會有兩個[1,2]的情況(搭配starting)或有[2, 1]和[1,2]的情況
如果初始給定的nums或candidates內容物為distinct integers或是unique elements，那就不用sort
通常會搭配
```python
if tmp not in self.res:
```
或是
```python
if nums[i] == nums[i - 1] and i > starting
continue
繼續呼叫self.dfs()
```
2. starting point
起始點永遠為自己(可重複)(i) or 比自己更大的數(i + 1)
```python
for i in range(starting, len(nums)):
self.dfs(i + 1, nums, path + nums[i])
```
3. 新增path再移除
```python
可以用非原地操作
path + nums[i]
# 不管是str還是list 都部會修改原始資料
取代
path.append(nums[i])
呼叫self.dfs()
path.remove(nums[i])
```
4. 結束條件
當和目標list一樣長
```python
if start == len(list):
self.res.append(path)
return
```
5. 結果長度限制
```python
如果任意長度都可以(例如subset或combination)
self.res.append(path.copy())
如果需要遞迴到底(結果長度都相同)(例如permutations)
if nums == []:
self.res.append(path.copy())
return
```
6. 複雜度
每個元素在遞迴過程中都有兩種(2)可能性：選擇該元素或不選擇該元素，時間複雜度為O(2^n) = O(branch^depth)，其中 branch 是每個節點的分支數aka可以選擇的數量，depth 是搜索的深度aka給定list的大小
backtracking O(n) 因為path，cascading O(2^n) 因為儲存tree
**:thumbsup:** 模板
法 1. Cascading
```python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subSet = [[]]
for n in nums:
for i in range(len(subSet)):
subNew = subSet[i].copy()
subNew.append(n) # 新增
subSet.append(subNew)
return subSet
```
法 2. Backtracking
```python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
self.traverse(nums, res, [], 0)
return res
def traverse(self, nums, res, path, start):
res.append(path)
for i in range(start, len(nums)):
self.traverse(nums, res, path + [nums[i]], i + 1)
```
兩者時間複雜度都相等O(n * 2^n)
---
**:thumbsup: 經典backtracking(subsets / combination sum)**
* subsets
```python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
self.traverse(nums, res, [], 0)
return res
def traverse(self, nums, res, path, start):
res.append(path)
for i in range(start, len(nums)):
self.traverse(nums, res, path + [nums[i]], i + 1)
```
* Subsets II
要記得需要有兩個括號[[]]，去當作初始值
不能有duplicate subset ex.[4,1], [1,4]
需要先sorted，這樣永遠會是跟"比自己大的數配對"
反例 : 假設有[4,1,4]，不會有[4,1], [1,4]等情況，可以確保只有[1,4]
時間複雜度O(n 2^n)
```python
class Solution:
def __init__(self):
self.res = [[]]
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
self.dfs(0, sorted(nums), [])
return self.res
def dfs(self, starting, nums, path):
if path not in self.res:
self.res.append(path.copy())
if starting == len(nums):
return
for i in range(starting, len(nums)):
self.dfs(i + 1, nums, path + [nums[i]])
```
* combination sum
自己可以重複
時間複雜度O(N^(T/M))
N candidates長度, T be the target value, and M be the minimal value among the candidates.
```python
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.res = []
self.backtracking(candidates, target, [], 0)
return self.res
def backtracking(self, candidates, target, path, start):
if sum(path) == target:
self.res.append(path)
if sum(path) > target:
return
for i in range(start, len(candidates)):
self.backtracking(candidates, target, path + [candidates[i]], i)
```
* Combination Sum II
給的list會有重複的數字，又輸出list不能有重複的，所以需要設定starting往後找和sort
時間複雜度O(2^n)，n為array size
```python
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
self.dfs(0, sorted(candidates), target, [])
return self.res
def dfs(self, starting, candidates, target, path):
if target < 0:
return
if target == 0:
self.res.append(path.copy())
for i in range(starting, len(candidates)):
if candidates[i] == candidates[i - 1] and i > starting:
continue
self.dfs(i + 1, candidates, target - candidates[i], path + [candidates[i]])
```
* Combination Sum III
可以用數字1-9中的k種相異數字去組成n
最差情況下，是9^k總組合
```python
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
self.res = []
def traverse(count, path, total, start):
if count > k or total > n:
return
if count == k and total == n:
self.res.append(path.copy())
for i in range(start, 10):
traverse(count + 1, path + [i], total + i, i + 1)
return
traverse(0, [], 0, 1)
return self.res
```
---
**:thumbsup: 其他經典backtracking(subsets / permutations)**
* Permutations
用dfs下去遍歷，用path去紀錄走過的路徑，當nums為空list時，即達成停止條件
```python
res = []
def dfs(rest_nums, path):
if len(path) == len(nums):
res.append(list(path))
for i in range(len(rest_nums)):
dfs(rest_nums[ : i] + rest_nums[i + 1 : ], path + [rest_nums[i]])
dfs(nums, [])
return res
```
* Combinations
```
Input: n = 4, k = 2 (length)
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
```
```python
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
self.res = []
self.traverse(n, k, [], 1)
return self.res
def traverse(self, n, k, path, start):
if len(path) == k:
self.res.append(list(path))
for i in range(start, n + 1):
self.traverse(n, k, path + [i], i + 1)
```
* subset內部加法(Partition Equal Subset Sum)
可以把題目簡化成能不能在給定list中，找到"list / 2"的數值
這種看"能不能在subset組成"的加法，基本上都是用樹枝，一邊加一邊不加
```python
# 初始化
record = set()
record.add(0)
for n in nums:
recordOld = record.copy()
for nOld in recordOld: # 用舊record跌代 防止set不停改變
record.add(nOld + n)
```
也可以用dp
dp[i][j]=true if the sum j can be formed by array elements in subset nums[0]..nums[i]
```python
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2:
return False
half = sum(nums) // 2
n = len(nums)
dp = [[False] * (half + 1) for _ in range(n + 1)] # (n + 1) * (half + 1)
dp[0][0] = True
for i in range(1, n + 1):
for j in range(half + 1):
cur = nums[i - 1]
if cur > j: # not include
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - cur]
return dp[n][half]
```
* Letter Combinations of a Phone Number
也是需要有starting，永遠地控制往後配對(index的部分)，letter的部分還是會每個都帶到
時間複雜度O(N * 4^N)，N為input list，4為每次最大可選擇的單字數量
```python
def backtracking(self, start, path, digits, hashmap):
if start == len(digits):
self.res.append(path)
return
for c in hashmap[digits[start]]:
self.backtracking(start + 1, path + c, digits, hashmap)
```
* Split a String Into the Max Number of Unique Substrings
用各種不同的subset數量去試，用visited去紀錄，不能有重複的subset
subset可能是start到end O(n) 個組合. backtracking O(2^n)，總共 O(n⋅2^n)
```python
class Solution:
def maxUniqueSplit(self, s: str) -> int:
self.res = 0
self.backtracking(s, 0, set())
return self.res
def backtracking(self, s, start, visited):
if start == len(s):
self.res = max(self.res, len(visited))
return
for end in range(start + 1, len(s) + 1):
sub_str = s[start : end]
if sub_str not in visited:
visited.add(sub_str)
self.backtracking(s, end, visited)
visited.remove(sub_str)
```
---
**:thumbsup: 其他**
* Next Permutation
1. 在全部都是升序的情況下，直接返回最小值(全部reverse)
2. 當出現124653，4是第一個非升序的，那就去搜索前面最靠近4，又比4大的數字(這樣可以得到比原本大一點點的值)，按順序搜索發現是5，那就把5和4交換，變成125643，再把5後面的643 reverse，變成346，得出答案125346
```python
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
small_i = n - 1
found = False
for i in range(n - 2, -1, -1):
if nums[i] < nums[i + 1]:
small_i = i
found = True
break
if not found:
# If no such element is found, reverse the entire array (last permutation case)
nums.reverse()
return
for i in range(n - 1, small_i, -1):
if nums[i] > nums[small_i]:
nums[small_i], nums[i] = nums[i], nums[small_i]
break
nums[small_i + 1:] = reversed(nums[small_i + 1:])
```
* Palindrome Partitioning 分割回文
檢查starting point和當前index區間，是否為palidrome
是的話拿剩下的字母繼續拆分
```python
class Solution:
def partition(self, s: str) -> List[List[str]]:
self.res = []
self.traverse(s, [], 0)
return self.res
def traverse(self, s, path, l):
if l == len(s):
self.res.append(list(path))
for i in range(l, len(s)):
if self.palidrome(s, l, i):
self.traverse(s, path + [s[l : i + 1]], i + 1)
def palidrome(self, s, l, r):
while l <= r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
```
* 棋盤(N-Queens)
棋盤的規則也包括斜對角不能重複，可利用左上右下(r - c)左下右上(r + c)數字相同的規則去紀錄
在dfs裡面，**用for迴圈去試下一行(r + 1)的每一個col，等於在dfs裡面有一個完整在跑col的for迴圈，在dfs前要加入set，在dfs後要remove from set**
```python
for c in range(n):
if 檢查是否違反條件:
continue
添加入set
dfs(r + 1, res)
移除從set
```
**總的時間複雜度為 N * (N-1) * (N-2) * … * 1，即 O(N!)**。
對於第一行，我們有 N 種選擇；對於第二行，由於要避免與第一行的皇后衝突，所以有 N-1 種選擇；對於第三行，由於要避免與前兩行的皇后衝突，所以有 N-2 種選擇；以此類推，直到最後一行。
* Sequential Digits
給定一low bound和一high bound，例如三位數與四位數，那裡面就會去遍歷每個三與四位數的數字
再來直接從1到最邊界的可能數字去組合，for i in range(9 - 數字的最小長度 + 1)，看是否在bound內，在的話就加入
```python
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
sample = "123456789"
lb, hb = len(str(low)), len(str(high))
res = list()
for length in range(lb, hb + 1): # go through different length
for i in range(len(sample) - length + 1):
# go through the number with specific length
num = int(sample[i : i + length])
if low <= num <= high:
res.append(num)
return res
```
---
**講解連結**
Provided by. me
###### tags: `recursion` `note` `code`
Sign in with Wallet
Connect another wallet