3 递归

sy115: 斐波拉契数列简单

https://sunnywhy.com/sfbj/4/3/115

给定正整数n，求斐波那契数列的第n项F(n)。

令表示斐波那契数列的第n项，它的定义是：

当n=1时，F(n)=1；

当n=2时，F(n)=1；

当n>2时，F(n) = F(n-1) + F(n-2)。

大数据版：斐波拉契数列-大数据版

输入描述

一个正整数n（ $1 \leq n \leq 25$ ）。

输出描述

斐波那契数列的第n项F(n)。

样例1

输入

输出

样例2

输入

输出

样例3

输入

输出

python

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

n = int(input())
print(fibonacci(n))

sy119: 汉诺塔中等

https://sunnywhy.com/sfbj/4/3/119

汉诺塔（又称河内塔）问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

抽象成模型就是说：

有三根相邻的柱子，标号分别为A、B、C，柱子按金字塔状叠放着n个不同大小的圆盘，现在要把所有盘子一个一个移动到柱子C上，并且任何时候同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，并给出具体的移动方案。

10(1).png

输入描述

一个正整数n（ $1 \leq n \leq 16$ ），表示圆盘的个数。

输出描述

第一行输出一个整数，表示至少需要的移动次数。

接下来每行输出一次移动，格式为X->Y，表示从柱子移动最上方的圆盘到柱子最上方。

样例1

输入

输出

1
A->C

样例2

输入

输出

复制

3
A->B
A->C
B->C

样例3

输入

输出

7
A->C
A->B
C->B
A->C
B->A
B->C
A->C

python

def move(n, s, t, middle):
    global cnt;ans
    if n == 1:
        cnt += 1
        ans.append(f'{s}->{t}')
    else:
        move(n-1, s, middle, t)
        move(1, s, t, middle)
        move(n-1, middle, t, s)


n = int(input())
cnt = 0
ans = []
move(n, 'A', 'C', 'B')
print(cnt)
print('\n'.join(ans))

sy126: 递归深度简单

https://sunnywhy.com/sfbj/4/3/126

斐波那契数列的定义：

text

令F(n)表示斐波那契数列的第n项，则：
当n=1时，F(n)=1；
当n=2时，F(n)=1；
当n>2时，F(n)=F(n-1)+F(n-2)。

下面是斐波那契数列问题的递归实现方式的伪代码：

text

F(n) {
    输出当前递归深度;
    if (n <= 2) {
        return 1;
    } else {
        return F(n - 1) + F(n - 2);
    }
}

其中在函数刚进来的时候输出了当前的递归深度（假设起始的递归深度为1），且递归每深入一层，递归深度加1。现在给定一个正整数，求在使用上述伪代码来计算斐波那契数列的过程中依次输出的递归深度。

输入描述

一个正整数n（ $2 \leq n \leq 12$ ）。

输出描述

每行输出一个数，依次输出当前递归深度。

样例1

输入

输出

样例2

输入

输出

样例3

输入

输出

1
2
2

样例4

输入

输出

python

def F(n, depth=0):
    depth += 1
    print(depth)
    if n <= 2:
        return 1
    else:
        return F(n-1, depth) + F(n-2, depth)

n = int(input())
if n == 1 or n == 2:
    print(1)
else:
    F(n)

sy127: 递归调试简单

https://sunnywhy.com/sfbj/4/3/127

斐波那契数列的定义：

text

令F(n)表示斐波那契数列的第n项，则：
当n=1时，F(n)=1；
当n=2时，F(n)=1；
当n>2时，F(n)=F(n-1)+F(n-2)。

下面是斐波那契数列问题的递归实现方式的伪代码：

text

F(n) {
    输出调试信息;
    if (n <= 2) {
        return 1;
    } else {
        return F(n - 1) + F(n - 2);
    }
}

递归代码的调试往往会很头疼，一个很重要的原因是在递归代码中输出的信息会因为多层而混在一起。但如果我们能在输出的调试信息前先输出一些和递归深度相关的数量的空格，就可以看出递归的层级，方便我们调试。例如当递归深度为1时先输出0个空格，递归深度为2时先输出4个空格，递归深度为3时先输出8个空格，以此类推，递归深度每多1，空格的个数就多4个）。

输入描述

一个正整数n（ $2 \leq n \leq 12$ ）。

输出描述

按题目描述的方式，每行输出调试信息，格式如下：

text

[与递归深度相关的一堆空格]n=具体值

样例1

输入

输出

n=1

样例2

输入

输出

n=2

样例3

输入

输出

n=3
    n=2
    n=1

样例4

输入

输出

n=4
    n=3
        n=2
        n=1
    n=2

样例5

输入

输出

python

def F(n, depth=0):
    depth += 1
    blank = ' ' * 4 * (depth-1)
    print(f"{blank}n={n}")
    if n <= 2:
        return 1
    else:
        return F(n-1, depth) + F(n-2, depth)

n = int(input())
if n == 1 or n == 2:
    print(f'n={n}')
else:
    F(n)

sy132: 全排列I 中等

https://sunnywhy.com/sfbj/4/3/132

给定一个正整数n，假设序列S=[1,2,3,...,n]，求S的全排列。

输入描述

一个正整数n（ $1 \leq n \leq 8$ ）。

输出描述

每个全排列一行，输出所有全排列。

输出顺序为：两个全排列A和B，若满足前k-1项对应相同，但有Ak < Bk，那么将全排列Ak优先输出（例如[1,2,3]比[1,3,2]优先输出）。

在输出时，全排列中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的全排列。

样例1

输入

输出

样例2

输入

输出

1 2
2 1

样例3

输入

输出

python

# 全排列I, https://sunnywhy.com/sfbj/4/3/132
list1 = []

def sequ(s, nums):
    if len(s) == nums:
        list1.append(s)
        return
    for i in range(1, nums + 1):
        if str(i) not in s:
            sequ(s + str(i), nums)

num = int(input())
sequ('', num)
for k in list1:
    print(' '.join(k))

全排列、八皇后，可以对照着学习。全排列I, https://sunnywhy.com/sfbj/4/3/132，02754 八皇后, http://cs101.openjudge.cn/practice/02754/
python
# 02754 八皇后, http://cs101.openjudge.cn/practice/02754/
list1 = []

def queen(s):
    if len(s) == 8:
        list1.append(s)
        return
    for i in range(1, 9):
        if all(str(i) != s[j] and abs(len(s) - j) != abs(i - int(s[j])) for j in range(len(s))):
            queen(s + str(i))

queen('')
samples = int(input())
for k in range(samples):
    print(list1[int(input()) - 1])

"""
abs(len(s) - j) != abs(i - int(s[j])) for j in range(len(s)) 是一个生成器表达式，
用于检查当前尝试放置的皇后是否与已经放置的皇后在同一条对角线上。具体解释如下：

- len(s) 表示当前已经放置的皇后的数量，即当前正在尝试放置的皇后的行号。
- j 是已经放置的皇后的列号。
- i 是当前尝试放置的皇后的列号。
- s[j] 是已经放置的皇后所在的列号。

对于每一个已经放置的皇后，检查以下条件：
- abs(len(s) - j) 计算当前尝试放置的皇后与已经放置的皇后之间的行差。
- abs(i - int(s[j])) 计算当前尝试放置的皇后与已经放置的皇后之间的列差。

如果行差和列差相等，说明两皇后在同一条对角线上，返回 `False`，否则返回 `True`。
"""
Note:
1）string类型是不可变的，作为参数传递给函数时，实际上是复制了一份，可以避免由于共享引用导致的数据污染问题。这样就会避免八皇后使用列表的浅拷贝问题。
2）因为列表是可变对象，当一个列表被传递给函数时，是传递该列表的引用。如果在函数内部直接修改了这个列表，那么这些修改也会影响到原始列表。
但是列表很方便，允许原地修改，可以提高性能并简化代码。使用时候注意浅拷贝问题就好。

python

maxn = 11
hashTable = [False] * maxn  # 当整数i已经在数组 P中时为 true

#@recviz
def increasing_permutaions(n, prefix=[]):
    if len(prefix) == n:  # 递归边界，已经处理完排列的1~位
        return [prefix]

    result = []
    for i in range(1, n + 1):
        if hashTable[i]:
            continue

        hashTable[i] = True  # 记i已在prefix中
        # 把i加入当前排列，处理排列的后续号位
        result += increasing_permutaions(n, prefix + [i])
        hashTable[i] = False  # 处理完为i的子问题，还原状态

    return result


n = int(input())
result = increasing_permutaions(n)
for r in result:
    print(' '.join(map(str,r)))

Backtracking based recursion/Permutations of given String https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

python

def generate_permutations(sequence, index=0):
    if index == len(sequence) - 1:
        return [sequence[:]]

    results = []
    for i in range(index, len(sequence)):
        # 交换当前元素与第一个未固定的元素
        sequence[index], sequence[i] = sequence[i], sequence[index]
        # 递归生成剩余部分的全排列
        results.extend(generate_permutations(sequence, index + 1))
        # 恢复交换，以便进行下一次迭代
        sequence[index], sequence[i] = sequence[i], sequence[index]

    return results


# 获取用户输入并生成全排列
num_elements = int(input())
numbers = list(range(1, num_elements + 1))
permutations = generate_permutations(numbers)

# 对所有排列按字典序排序
permutations.sort()

# 输出所有排列
for perm in permutations:
    print(' '.join(map(str, perm)))

如果不使用 sort 来实现字典序输出，可以在递归生成全排列时确保元素按顺序递归选择，避免打乱顺序。通过总是从当前子序列的第一个元素开始递归，这样生成的全排列就会自然地按字典序排列。即对于 n>=2 时，只需依次将 1 到 n 放在首位，将其余数所有全排列加在后面即可。

Method The idea is to one by one extract all elements, place them at first position and recur for remaining list. https://www.geeksforgeeks.org/generate-all-the-permutation-of-a-list-in-python/

python

def generate_permutations(sequence):
    # 如果序列长度为1，直接返回它的全排列
    if len(sequence) == 1:
        return [sequence]
    else:
        results = []
        for i in range(len(sequence)):
            # 创建一个新序列，将当前元素移除
            remaining_sequence = sequence[:i] + sequence[i+1:]
            # 递归生成剩余部分的全排列
            for result in generate_permutations(remaining_sequence):
                # 将当前元素加入到排列前，保证字典序
                results.append([sequence[i]] + result)
        return results

# 获取用户输入并生成全排列
num_elements = int(input())
numbers = list(range(1, num_elements + 1))
str_numbers = list(map(str, numbers))

# 输出所有排列，已按字典序
for result in generate_permutations(str_numbers):
    print(' '.join(result))

python

# 胡云皓 光华管理学院
def qpl(n, lst, m):
    if n == 1:
        print(*lst, sep=' ')
        return
    for i in range(1, m):
        if not i in lst:
            qpl(n - 1, lst + [i], m)
m = int(input()) + 1
qpl(m,[], m)

数据量太小可以大复杂度搜索。循环遍历+回溯即可。

python

# 高景行 数学科学学院
n = int(input())
def g(m, a, used):
    global n
    if m > n:
        print(" ".join(map(str, a)))
        return
    for i in range(1, n + 1):
        if not used[i]:
            used[i] = True
            a.append(i)
            g(m + 1, a, used)
            used[i] = False
            a.pop()
    return
a = []
g(1, a, [False] * (n + 1))

python

# 谢昊宸 数学学院
def permutation(lst):
    n = len(lst)
    if n == 1:
        return [[lst[0]]]
    else:
        ans = []
        for i in range(0, n):
            new_lst = lst[:i] + lst[i + 1 :]
            for arr in permutation(new_lst):
                ans.append([lst[i]] + arr)
        return ans


n = int(input())
lst = list(range(1, n + 1))
for arr in permutation(lst):
    for i in range(n):
        if i != n - 1:
            print(arr[i], end=" ")
        else:
            print(arr[i])

吴诚舟-24物理学院，若不给tag最先想到cantor_expansion。没有独立想出如何用递归来解。

python

#cantor_expansion
from math import factorial

def cantor_to_permutation(x, n):
    li = [i for i in range(1, n+1)]
    ret = [0]*n
    for j in range(n-1, 0, -1):
        index = x // factorial(j)
        x %= factorial(j)
        ret[n-1-j] = li[index]
        del li[index]
    ret[-1] = li.pop()
    return ret

n = int(input())
for i in range(factorial(n)):
    print(*cantor_to_permutation(i, n))

感觉回溯的想法很神奇，可以轻松搞出树状结构

python

def P(l, depth):
    if depth == n:
        ans.append(path[:])
        return
    for i, pos in enumerate(l):
        if not used[i]:
            used[i] = 1
            path.append(f"{pos}")
            P(l, depth + 1)
            path.pop()
            used[i] = 0

n = int(input())
l = list(range(1, n + 1))
used = [0 for i in range(n)]
depth = 0
ans, path = [], []
P(l, 0)
for i in ans:
    print(" ".join(i))

python

def quan(yu, a):
    b = []
    if len(a) == 1:
        b.append(' '.join(map(str, yu+a)))
        return b

    for i in a:
        f = quan(yu+[i], [j for j in a if j != i])
        b.extend(f)

    return b

n = int(input())
ans = quan([], list(range(1, n+1)))
print("\n".join(ans))

python

n = int(input())
l = []
for i in range(1,n+1):
    l.append(f'{i}')

def arrange(l):
    if len(l) == 1:
        """
        当列表中只有一个元素时，使用yield关键字返回这个元素。这里使用了生成器，而不是直接返回（return）值，
        这意味着函数可以暂停执行并在需要时恢复，这对于处理大量数据或递归调用非常有用。
        """
        yield l[0]
    else:
        for i in range(len(l)):
            new_l = l[:i] + l[i+1:]
            for rest in arrange(new_l):
                yield l[i] + ' ' + rest

for ans in arrange(l):
    print(ans)

yield 是 Python 中用于定义生成器函数的关键字。生成器是一种特殊的迭代器，它允许你在函数内部逐步生成值，而不是一次性生成所有值并将它们存储在内存中。当你在函数中使用 yield 语句时，这个函数就变成了一个生成器。当调用生成器函数时，它不会立即执行函数体内的代码，而是返回一个生成器对象。只有当这个生成器对象被迭代时，才会执行函数体内的代码，直到遇到 yield 语句，此时函数会暂停执行，并返回 yield 后面的表达式的值。当再次迭代生成器时，函数会从上次暂停的地方继续执行，直到遇到下一个 yield 语句，依此类推，直到函数执行完毕。
yield 与 return 的区别
执行时机：当函数中使用 return 时，函数会立即终止执行，并返回一个值；而使用 yield 时，函数会生成一个生成器对象，该对象可以在需要时逐步产生值。
内存占用：return 需要一次性计算并返回所有的值，如果这些值的数量很大，可能会消耗大量的内存。相比之下，yield 可以按需生成值，因此更加节省内存。
可迭代性：使用 return 的函数只能返回一次值，而使用 yield 的生成器可以多次产生值，使得生成器可以用于迭代。
状态保持：yield 使函数能够记住其上一次的状态，包括局部变量和执行的位置，因此当生成器再次被调用时，它可以从中断的地方继续执行。而 return 则不会保存任何状态信息，每次调用都是全新的开始。
使用 yield 的好处
节省资源：由于生成器是惰性求值的，只有在需要的时候才计算下一个值，所以它可以有效地处理大数据集，避免一次性加载所有数据到内存中。
简化代码：生成器提供了一种简单的方式来实现复杂的迭代模式，而不需要显式地管理迭代状态。
提高效率：对于需要连续处理大量数据的应用场景，生成器可以避免不必要的内存分配和垃圾回收，从而提高程序的运行效率。
易于使用：生成器可以像普通迭代器一样使用，可以很容易地集成到现有的代码中，如 for 循环等。
综上所述，yield 提供了一种强大的机制，用于处理那些需要逐步生成或处理大量数据的情况，同时保持代码的简洁性和高效性。

sy133: 全排列II 中等

https://sunnywhy.com/sfbj/4/3/133

给定一个长度为n的序列，其中有n个互不相同的正整数，求该序列的所有全排列。

输入描述

第一行一个正整数n（ $1 \leq n \leq 8$ ），表示序列中的元素个数。

第二行按升序给出n个互不相同的正整数（每个正整数均不超过100）。

输出描述

每个全排列一行，输出所有全排列。

输出顺序为：两个全排列A和B，若满足前k-1项对应相同，但有 $A_{k} < B_{k}$ ，那么将全排列A优先输出（例如[1,2,3]比[1,3,2]优先输出）。

在输出时，全排列中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的全排列。

样例1

输入

3
1 2 3

输出

样例2

输入

2
3 5

输出

3 5
5 3

python

n = int(input())
nums = list(map(int, input().split()))

ans, sol = [], []
def backtrack():
    if len(sol) == n:
        ans.append(sol[:])
        return
    for i in nums:
        if i not in sol:
            sol.append(i)
            backtrack()
            sol.pop()
backtrack()
for a in ans:
    print(*a)

sy134: 全排列III 中等

https://sunnywhy.com/sfbj/4/3/134

给定一个长度为n的序列，其中有n个可能重复的正整数，求该序列的所有全排列。

输入描述

第一行一个正整数n（ $1 \leq n \leq 8$ ），表示序列中的元素个数。

第二行按升序给出n个可能重复的正整数（每个正整数均不超过100）。

输出描述

每个全排列一行，输出所有全排列。

输出顺序为：两个全排列A和B，若满足前k-1项对应相同，但有 $A_{k} < B_{k}$ ，那么将全排列A优先输出（例如[1,2,3]比[1,3,2]优先输出）。

在输出时，全排列中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的全排列。

样例1

输入

3
1 1 3

输出

1 1 3
1 3 1
3 1 1

python

n = int(input())
nums = list(map(int, input().split()))

ans, sol = set(), []
used = [False] * n

def backtrack():
    if len(sol) == n:
        ans.add(tuple(sol))
        return

    for i in range(n):
        if not used[i]:
            used[i] = True
            sol.append(nums[i])
            backtrack()
            sol.pop()
            used[i] = False

backtrack()

for a in sorted(ans):
    print(*a)

有2处剪枝。必须按 位置（索引） 来判断是否使用过，而不是按值。

python

from typing import List

class Solution:
    #def permute(self, nums: List[int]) -> List[List[int]]:
    def permute(self, nums: List[int]) -> set[tuple]:
        n = len(nums)
        # ans, sol = [], []
        ans, sol = set(), []
        used = [False] * n  # ← 新增：记录每个位置是否用过

        def backtrack():
            # 终止条件：当前排列已满
            if len(sol) == n:
                # ans.append(sol[:])  # 深拷贝
                ans.add(tuple(sol))
                return

            # 尝试每个未被使用的数
            #for x in nums:
            for i in range(n):
                if used[i]:
                    continue
                # 去重剪枝：相同值且前一个未使用，则跳过（保证字典序+去重）
                if i>0 and nums[i-1]==nums[i] and used[i-1]:
                    continue
                used[i] = True
                sol.append(nums[i])  # 选择
                backtrack()  # 递归
                sol.pop()  # 回溯
                used[i] = False

        nums.sort()
        backtrack()
        return ans

if __name__ == '__main__':
    sol = Solution()
    n = int(input())
    a = list(map(int, input().split()))
    result = sol.permute(a)
    for perm in sorted(result):
        print(*perm)

sy135: 组合I 中等

https://sunnywhy.com/sfbj/4/3/135

给定两个正整数n、k，假设序列S=[1,2,3,...,n]，求S从中任选k个的所有可能结果。

输入描述

两个正整数n、k（ $1 \leq k \leq n \leq 12$ ）。

输出描述

每个组合一行，输出所有组合。

输出顺序为：两个组合A和B，若各自升序后满足前项对应相同，但有 $A_{k} < B_{k}$ ，那么将组合优先输出（例如比优先输出）。

在输出组合时，组合内部按升序输出，组合中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的组合。

样例1

输入

2 1

输出

1
2

样例2

输入

4 2

输出

python

def generate_combinations(n, k):
    def backtrack(start, path):
        if len(path) == k:
            combinations.append(list(path))
            return
        
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    
    combinations = []
    backtrack(1, [])
    return combinations

def main():
    n, k = map(int, input().split())
    combinations = generate_combinations(n, k)
    
    for comb in combinations:
        print(" ".join(map(str, comb)))

if __name__ == "__main__":
    main()

sy136: 组合II 中等

https://sunnywhy.com/sfbj/4/3/136

给定一个长度为n的序列，其中有n个互不相同的正整数，再给定一个正整数k，求从序列中任选k个的所有可能结果。

输入描述

两个正整数n、k（ $1 \leq k \leq n \leq 12$ ）。

第二行按升序给出n个互不相同的正整数（每个正整数均不超过100）。

输出描述

每个组合一行，输出所有组合。

输出顺序为：两个组合A和B，若各自升序后满足前项对应相同，但有 $A_{k} < B_{k}$ ，那么将组合优先输出（例如比优先输出）。

在输出组合时，组合内部按升序输出，组合中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的组合。

样例1

输入

3 2
1 2 3

输出

1 2
1 3
2 3

样例2

输入

2 1
3 5

输出

3
5

python

def combine(n, k, nums):
    ans, sol = [], []
    N = len(nums)

    def backtrack(i):
        # 当前组合已满
        if len(sol) == k:
            ans.append(sol[:])
            return
        # 剩余元素不足以凑满 k 个，剪枝
        if len(sol) + (N - i) < k:
            return
        # 到达末尾
        if i == N:
            return

        # 先“选” nums[i]
        sol.append(nums[i])
        backtrack(i + 1)
        sol.pop()

        # 再“不选” nums[i]
        backtrack(i + 1)

    backtrack(0)
    return ans


# 读取并输出
if __name__ == "__main__":
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    res = combine(n, k, a)
    for comb in res:
        print(*comb)

python

def generate_combinations(n, k, nums):
    def backtrack(start, path):
        if len(path) == k:
            combinations.append(list(path))
            return
        
        for i in range(start, n):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    combinations = []
    backtrack(0, [])
    return combinations

def main():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    combinations = generate_combinations(n, k, nums)
    
    for comb in combinations:
        print(" ".join(map(str, comb)))

if __name__ == "__main__":
    main()

sy137: 组合III 中等

https://sunnywhy.com/sfbj/4/3/137

给定一个长度为n的序列，其中有n个可能重复的正整数k，再给定一个正整数k，求从序列中任选k个的所有可能结果。

输入描述

两个正整数n、k（ $1 \leq k \leq n \leq 12$ ）。

第二行按升序给出n个互不相同的正整数（每个正整数均不超过100）。

输出描述

每个组合一行，输出所有组合。

输出顺序为：两个组合A和B，若各自升序后满足前项对应相同，但有 $A_{k} < B_{k}$ ，那么将组合优先输出（例如比优先输出）。

在输出组合时，组合内部按升序输出，组合中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的组合。

样例1

输入

3 2
1 1 3

输出

1 1
1 3

python

def solve():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    nums.sort()  # 输入已升序，但保险
    
    sol = []
    ans = set()   # 用 set 去重
    N = len(nums)

    def backtrack(i):
        # 选满 k 个则加入 set
        if len(sol) == k:
            ans.add(tuple(sol))
            return
        # 剩余元素不足以凑够 k 个，剪枝
        if len(sol) + (N - i) < k:
            return
        if i == N:
            return

        # 1. 选 nums[i]
        sol.append(nums[i])
        backtrack(i + 1)
        sol.pop()

        # 2. 不选 nums[i]
        backtrack(i + 1)

    backtrack(0)

    # 将所有组合按字典序排序
    res = sorted(ans)

    # 输出
    for comb in res:
        print(*comb)

solve()

python

def generate_combinations(n, k, nums):
    def backtrack(start, path):
        if len(path) == k:
            combinations.add(tuple(path))
            return
        
        for i in range(start, n):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    combinations = set()
    backtrack(0, [])
    return sorted(combinations)

def main():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    combinations = generate_combinations(n, k, nums)
    
    for comb in combinations:
        print(" ".join(map(str, comb)))

if __name__ == "__main__":
    main()

sy146: 判断八皇后简单

https://sunnywhy.com/sfbj/4/3/146

在8×8的国际棋盘上摆放了8个皇后，判断其是否是一个合法的摆放方式，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

输入描述

输入8行，每行为8个用空格隔开的整数，取值为0或1，其中1表示该位置是皇后，0则表示不是皇后。

输出描述

如果该摆放方式是合法的，那么输出YES，否则输出NO。

样例1

输入

0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0

输出

YES

样例2

输入

0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0

输出

NO

这个题可以直接用集合判断是否有冲突，非常简洁。解题思路：

对于八皇后问题：

每一行必须恰好有 1 个皇后。
任意两个皇后不能在同一列。
任意两个皇后不能在同一条对角线上。

对角线分为两种：

主对角线（左上 ↘ 右下）：行号 - 列号相同。
副对角线（左下 ↗ 右上）：行号 + 列号相同。

我们只要收集所有皇后的位置 (r, c)，然后看：

行数、列数、(r-c)、(r+c) 四个集合的长度是否都是 8。

python

board = [list(map(int, input().split())) for _ in range(8)]

rows = set()
cols = set()
diag1 = set()  # r - c
diag2 = set()  # r + c

queens = 0

for r in range(8):
    for c in range(8):
        if board[r][c] == 1:
            queens += 1
            rows.add(r)
            cols.add(c)
            diag1.add(r - c)
            diag2.add(r + c)

if queens == 8 and len(rows) == len(cols) == len(diag1) == len(diag2) == 8:
    print("YES")
else:
    print("NO")

为了判断一个8×8的国际象棋棋盘上的8个皇后是否合法摆放，我们需要确保任意两个皇后不能处于同一行、同一列或同一斜线上。我们可以使用以下步骤来实现这一目标：

读取输入：读取8行，每行8个用空格隔开的整数，表示棋盘上的位置。
检查行和列：确保每一行和每一列只有一个皇后。
检查对角线：确保任意两个皇后不在同一对角线上。

i = j + k 或者 i = -j + k，其中k是斜率。

python

def is_valid_board(board):
    n = 8
    rows = [0] * n
    cols = [0] * n
    diag1 = [0] * (2 * n - 1)
    diag2 = [0] * (2 * n - 1)
    
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                rows[i] += 1
                cols[j] += 1
                diag1[i + j] += 1
                diag2[i - j] += 1
                
                if rows[i] > 1 or cols[j] > 1 or diag1[i + j] > 1 or diag2[j - i + n - 1] > 1:
                    return "NO"
    
    return "YES"

def main():
    board = []
    for _ in range(8):
        row = list(map(int, input().split()))
        board.append(row)
    
    result = is_valid_board(board)
    print(result)

if __name__ == "__main__":
    main()

sy147: 八皇后问题

https://sunnywhy.com/sfbj/4/3/147

在8×8的国际棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

python

def solve_n_queens(n):
    def is_safe(board, row, col):
        # 检查列是否有皇后
        for i in range(row):
            if board[i][col] == 1:
                return False

        # 检查左上对角线是否有皇后
        for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
            if board[i][j] == 1:
                return False

        # 检查右上对角线是否有皇后
        for i, j in zip(range(row, -1, -1), range(col, n)):
            if board[i][j] == 1:
                return False

        return True

    def backtrack(row):
        if row == n:
            solutions.append([''.join(map(str,row)) for row in board])
            return

        for col in range(n):
            if is_safe(board, row, col):
                board[row][col] = 1
                backtrack(row + 1)
                board[row][col] = 0

    n = 8
    board = [[0] * n for _ in range(n)]
    solutions = []
    backtrack(0)
    return len(solutions)


def main():
    result = solve_n_queens(8)
    print(result)


if __name__ == "__main__":
    main()

backtrack 函数：如果已经放置了 n 个皇后，将当前解决方案转换为字符串形式并添加到 solutions 列表中。遍历当前行的每一列，如果在该位置放置皇后是安全的，则放置皇后并递归调用 backtrack 处理下一行。递归返回后，恢复当前状态（即回溯）。

sy148: N皇后问题

https://sunnywhy.com/sfbj/4/3/148

在n x n的国际棋盘上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

输入描述

一个正整数n（ $1 \leq n \leq 10$ ）。

输出描述

输出一个整数，表示摆法种数。

样例1

输入

输出

使用一维数组来表示棋盘是一种常见的优化方法，特别是对于 n 皇后问题。一维数组的每个元素表示每一行的皇后所在的列。这样可以减少空间复杂度，并且使代码更加简洁和高效。

为什么使用一维数组？

空间效率：一维数组只需要 O(n) 的空间，而二维数组需要 O(n^2) 的空间。
简化检查：在一维数组中，检查列和对角线冲突更加简单。
易于回溯：一维数组更容易进行回溯操作。

python

def solve_n_queens(n):
    def is_safe(row, col):
        # 检查列是否有皇后
        for i in range(row):
            if board[i] == col or \
               board[i] - i == col - row or \
               board[i] + i == col + row:
                return False
        return True

    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1  # 回溯

    solutions = []
    board = [-1] * n
    backtrack(0)
    return len(solutions)

def main():
    n = int(input())
    result = solve_n_queens(n)
    print(result)

if __name__ == "__main__":
    main()

3 递归 ​

sy115: 斐波拉契数列 简单 ​

sy119: 汉诺塔 中等 ​

sy126: 递归深度 简单 ​

sy127: 递归调试 简单 ​

sy132: 全排列I 中等 ​

sy133: 全排列II 中等 ​

sy134: 全排列III 中等 ​

sy135: 组合I 中等 ​

sy136: 组合II 中等 ​

sy137: 组合III 中等 ​

sy146: 判断八皇后 简单 ​

sy147: 八皇后问题 ​

sy148: N皇后问题 ​

3 递归

sy115: 斐波拉契数列简单

sy119: 汉诺塔中等

sy126: 递归深度简单

sy127: 递归调试简单

sy132: 全排列I 中等

sy133: 全排列II 中等

sy134: 全排列III 中等

sy135: 组合I 中等

sy136: 组合II 中等

sy137: 组合III 中等

sy146: 判断八皇后简单

sy147: 八皇后问题

sy148: N皇后问题