---
# System prepended metadata

title: '**程式筆記(recursion)**'
tags: [recursion, code, note]

---

# **程式筆記(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
![image](https://hackmd.io/_uploads/Sknq29rxkl.png =70%x)
```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
![image](https://hackmd.io/_uploads/BJpGkjHeyl.png =50%x)
```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)
![image](https://hackmd.io/_uploads/S1zbA0EU6.png =50%x)
![image](https://hackmd.io/_uploads/H1wtJjHlJg.png =50%x)

```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
自己可以重複
![image](https://hackmd.io/_uploads/BkqvscSeyx.png)
時間複雜度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
    ![image](https://hackmd.io/_uploads/Sktnf1r8p.png =70%x)
![image - Copy (3)](https://hackmd.io/_uploads/ry-QLJdeyg.png)

```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時，即達成停止條件
![](https://hackmd.io/_uploads/H13Xr8KKh.png)
```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組成"的加法，基本上都是用樹枝，一邊加一邊不加
![](https://hackmd.io/_uploads/BJnzRMECh.png =70%x)

```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]
![image](https://hackmd.io/_uploads/BJCh31uekl.png)

```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
![image](https://hackmd.io/_uploads/SJCGc84ekl.png =50%x)
用各種不同的subset數量去試，用visited去紀錄，不能有重複的subset
![image](https://hackmd.io/_uploads/ryN69UEeye.png =70%x)

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
是的話拿剩下的字母繼續拆分
![image](https://hackmd.io/_uploads/ryHxjJSI6.png)

```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`