Medium

题目描述

给你一个整数数组 nums ，返回所有长度至少为 2 的不同非递减子序列。答案中的子序列可以按任意顺序排列。

示例 1：

输入: nums = [4,6,7,7]
输出: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入: nums = [4,4,3,2,1]
输出: [[4,4]]

提示：

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

解题思路

这道题要求找出所有长度至少为2的非递减子序列。由于数组长度较小（最多15个元素），可以使用回溯算法来枚举所有可能的子序列。

核心思路：

  1. 回溯枚举：对于每个位置的元素，都有选择和不选择两种情况
  2. 非递减约束：当前元素必须不小于路径中的最后一个元素
  3. 去重处理：由于要求"不同"的子序列，需要在每一层递归中去重

去重的关键在于：在同一层递归中，相同的数字只能选择一次。这可以通过集合（Set）来实现，记录当前递归层已经使用过的数字。

算法流程：

  1. 从数组第一个位置开始回溯
  2. 对于每个位置，如果当前数字满足非递减条件且未在当前层使用过，则可以选择
  3. 选择后递归处理下一个位置
  4. 当路径长度≥2时，将当前路径加入结果集
  5. 回溯时移除最后添加的元素

时间复杂度主要由子序列数量决定，在最坏情况下可能达到O(2^n)。

代码实现

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    
    void backtrack(vector<int>& nums, int startIndex) {
        if (path.size() >= 2) {
            result.push_back(path);
        }
        
        unordered_set<int> used;
        for (int i = startIndex; i < nums.size(); i++) {
            if (!path.empty() && nums[i] < path.back()) continue;
            if (used.count(nums[i])) continue;
            
            used.insert(nums[i]);
            path.push_back(nums[i]);
            backtrack(nums, i + 1);
            path.pop_back();
        }
    }
    
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtrack(nums, 0);
        return result;
    }
};

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []
        
        def backtrack(start_index):
            if len(path) >= 2:
                result.append(path[:])
            
            used = set()
            for i in range(start_index, len(nums)):
                if path and nums[i] < path[-1]:
                    continue
                if nums[i] in used:
                    continue
                
                used.add(nums[i])
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()
        
        backtrack(0)
        return result

public class Solution {
    private IList<IList<int>> result = new List<IList<int>>();
    private List<int> path = new List<int>();
    
    private void Backtrack(int[] nums, int startIndex) {
        if (path.Count >= 2) {
            result.Add(new List<int>(path));
        }
        
        HashSet<int> used = new HashSet<int>();
        for (int i = startIndex; i < nums.Length; i++) {
            if (path.Count > 0 && nums[i] < path[path.Count - 1]) continue;
            if (used.Contains(nums[i])) continue;
            
            used.Add(nums[i]);
            path.Add(nums[i]);
            Backtrack(nums, i + 1);
            path.RemoveAt(path.Count - 1);
        }
    }
    
    public IList<IList<int>> FindSubsequences(int[] nums) {
        Backtrack(nums, 0);
        return result;
    }
}

var findSubsequences = function(nums) {
    const result = [];
    const path = [];
    
    const backtrack = (startIndex) => {
        if (path.length >= 2) {
            result.push([...path]);
        }
        
        const used = new Set();
        for (let i = startIndex; i < nums.length; i++) {
            if (path.length > 0 && nums[i] < path[path.length - 1]) continue;
            if (used.has(nums[i])) continue;
            
            used.add(nums[i]);
            path.push(nums[i]);
            backtrack(i + 1);
            path.pop();
        }
    };
    
    backtrack(0);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(2^n × n)，其中n为数组长度。最坏情况下需要遍历所有可能的子序列，每个子序列的复制需要O(n)时间
空间复杂度O(n)，递归调用栈的深度最多为n，路径数组最多包含n个元素

相关题目