如何求解数组中元素个数恰好为N的所有子序列

问题需求：给定任意数组，输出所有由恰好N个元素组成的子序列。子序列需保持原数组的元素相对顺序，不允许重复。
示例输入：arr = [1,2,3,4]，N=3
示例输出：[[1,2,3], [1,2,4], [1,3,4], [2,3,4]]

核心思路 #

这个问题本质是求数组的N元无重复组合，组合的特性就是元素顺序和原数组保持一致，刚好匹配子序列的定义要求。

实现方案 #

方案1：手写回溯算法（无第三方依赖） #

回溯是最通用的实现方式，不受编程语言限制，时间复杂度为$O(C(k,n))$，其中$C(k,n)$是从k个元素选n个的组合数，是该问题的最优时间复杂度。
代码示例（Python）：

def find_n_length_subsequences(arr, n):
    result = []
    def backtrack(start_idx, current_path):
        # 已选元素数量达标，存入结果
        if len(current_path) == n:
            result.append(current_path.copy())
            return
        # 剩余可选元素数量不够时直接剪枝，优化性能
        if len(arr) - start_idx < n - len(current_path):
            return
        for i in range(start_idx, len(arr)):
            current_path.append(arr[i])
            backtrack(i + 1, current_path)
            current_path.pop()
    backtrack(0, [])
    return result

# 测试
print(find_n_length_subsequences([1,2,3,4], 3))
# 输出：[[1,2,3], [1,2,4], [1,3,4], [2,3,4]]

方案2：调用内置组合函数 #

大部分主流编程语言都有内置的组合计算工具，可直接调用简化代码：
Python示例（使用itertools.combinations）：

from itertools import combinations

arr = [1,2,3,4]
n = 3
res = [list(item) for item in combinations(arr, n)]
print(res)
# 输出与上述一致

内容的提问来源于stack exchange，提问作者myTest532 myTest532