递增子序列

491. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 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

相似题目

最长数对链

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<vector<int>> findSubsequences(vector<int>& nums) { } };

golang 解法, 执行用时: 16 ms, 内存消耗: 12.1 MB, 提交时间: 2022-12-25 11:55:14

var (
    temp []int
    ans [][]int
)

func findSubsequences(nums []int) [][]int {
    ans = [][]int{}
    dfs(0, math.MinInt32, nums)
    return ans
}

func dfs(cur, last int, nums []int) {
    if cur == len(nums) {
        if len(temp) >= 2 {
            t := make([]int, len(temp))
            copy(t, temp)
            ans = append(ans, t)
        }
        return
    }
    if nums[cur] >= last {
        temp = append(temp, nums[cur])
        dfs(cur + 1, nums[cur], nums)
        temp = temp[:len(temp)-1]
    }
    if nums[cur] != last {
        dfs(cur + 1, last, nums)
    }
}

golang 解法, 执行用时: 112 ms, 内存消耗: 13.6 MB, 提交时间: 2022-12-25 11:54:55

var (
    n int
    temp []int
)
func findSubsequences(nums []int) [][]int {
    n = len(nums)
    ans := [][]int{}
    set := map[int]bool{}
    for i := 0; i < 1 << n; i++ {
        findSubsequences1(i, nums)
        hashValue := getHash(263, int(1e9 + 7))
        if check() && !set[hashValue] {
            t := make([]int, len(temp))
            copy(t, temp)
            ans = append(ans, t)
            set[hashValue] = true
        }
    }
    return ans
}

func findSubsequences1(mask int, nums []int) {
    temp = []int{}
    for i := 0; i < n; i++ {
        if (mask & 1) != 0 {
            temp = append(temp, nums[i])
        }
        mask >>= 1
    }
}

func getHash(base, mod int) int {
    hashValue := 0
    for _, x := range temp {
        hashValue = hashValue * base % mod + (x + 101)
        hashValue %= mod
    }
    return hashValue
}

func check() bool {
    for i := 1; i < len(temp); i++ {
        if temp[i] < temp[i - 1] {
            return false
        }
    }
    return len(temp) >= 2
}

javascript 解法, 执行用时: 136 ms, 内存消耗: 56.5 MB, 提交时间: 2022-12-25 11:54:25

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const findSubsequences = (nums) => {
  const res = [];
  const len = nums.length;

  const dfs = (start, path) => {
    if (start == len) {    // 递归的出口，指针已经越界
      if (path.length >= 2) {   // path长度大于等于2
        res.push(path.slice()); // 加入解集
        return;
      }
    }
    path.push(nums[start]);         // 进行选择
    for (let i = start + 1; i <= len; i++) { //枚举出选项，从start+1到len都可以选
      const prev = nums[start];     // 递归树中上一层的选择
      const cur = nums[i];          // 当前的选择
      if (i < len && cur == prev) { // i还没越界，且当前选择和上一层的选择相同
        dfs(i, path);               // 递归完当前选择，就break，避免i自增，导致i==len
        break;                      // 从而避免导致执行else if里的逻辑，导致start==len
                                    // 导致来递归的出口，path推入res
      } else if (i == len || prev < cur) { // i==len越界，让它落入递归，在递归的出口中return
        dfs(i, path);                      // 或prev < cur，满足条件，往下递归
      }
    }
    path.pop();                     // 撤销选择
  };
  for (let i = 0; i < len; i++) {
    dfs(i, []);
  }
  return res;
};

java 解法, 执行用时: 4 ms, 内存消耗: 46.8 MB, 提交时间: 2022-12-25 11:53:10

class Solution {
    // 定义全局变量保存结果
    List<List<Integer>> res = new ArrayList<>();
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        // idx 初始化为 -1，开始 dfs 搜索。
        dfs(nums, -1, new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums, int idx, List<Integer> curList) {
        // 只要当前的递增序列长度大于 1，就加入到结果 res 中，然后继续搜索递增序列的下一个值。
        if (curList.size() > 1) {
            res.add(new ArrayList<>(curList));
        }

        // 在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值。
        // 借助 set 对 [idx + 1, nums.length - 1] 范围内的数去重。
        Set<Integer> set = new HashSet<>();
        for (int i = idx + 1; i < nums.length; i++) {
            // 1. 如果 set 中已经有与 nums[i] 相同的值了，说明加上 nums[i] 后的所有可能的递增序列之前已经被搜过一遍了，因此停止继续搜索。
            if (set.contains(nums[i])) { 
                continue;
            }
            set.add(nums[i]);
            // 2. 如果 nums[i] >= nums[idx] 的话，说明出现了新的递增序列，因此继续 dfs 搜索（因为 curList 在这里是复用的，因此别忘了 remove 哦）
            if (idx == -1 || nums[i] >= nums[idx]) {
                curList.add(nums[i]);
                dfs(nums, i, curList);
                curList.remove(curList.size() - 1);
            }
        }
    }
}

python3 解法, 执行用时: 84 ms, 内存消耗: 21.4 MB, 提交时间: 2022-12-12 14:51:22

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []
        d = deque([(nums, [])])
        while d:
            cur, new = d.popleft()
            if len(new) > 1:
                res.append(new)
            curPres = set()
            for inx, i in enumerate(cur):
                if i in curPres:
                    continue
                if not new or i >= new[-1]:
                    curPres.add(i)
                    d.append((cur[inx+1:], new+[i]))
        return res

python3 解法, 执行用时: 64 ms, 内存消耗: 20.9 MB, 提交时间: 2022-12-12 14:51:10

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []

        def dfs(nums: List[int], tmp: List[int]) -> None:
            if len(tmp) > 1:
                res.append(tmp)
            curPres = set()
            for inx, i in enumerate(nums):
                if i in curPres:
                    continue
                if not tmp or i >= tmp[-1]:
                    curPres.add(i)
                    dfs(nums[inx+1:], tmp+[i])

        dfs(nums, [])
        return res

python3 解法, 执行用时: 56 ms, 内存消耗: 24.4 MB, 提交时间: 2022-12-12 14:50:38

'''
动态规划 + 哈希表
'''
class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        pres = {(nums[0], )}
        for i in nums[1:]:
            pres.update({j+(i, ) for j in pres if j[-1] <= i})
            pres.add((i, ))
        return [list(i) for i in pres if len(i) > 1]

javascript 解法, 执行用时: 136 ms, 内存消耗: 57.3 MB, 提交时间: 2022-12-12 14:49:02

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function (nums) {

    //记录结果
    let result = []
    //记录子序列
    let path = []

    //回溯主体
    function backtracing(start) {
        if (path.length > 1) {
            result.push([...path])
        }
        //用数组作为哈希表，记录以及使用过的元素，每次新的递归开始后used都会被重新定义
        let used = []
        for (let i = start; i < nums.length; i++) {
            //当所取元素小于子序列的最后一个 || 所取元素在本层循环使用过
            //nums[i] + 100是为了保证uset数组下标>=0，因为-100 <= nums[i] <= 100
            if ((path.length > 0 && nums[i] < path[path.length - 1]) || used[nums[i] + 100]) {
                continue
            }
            used[nums[i] + 100] = true
            path.push(nums[i])
            backtracing(i + 1)
            path.pop()
        }
    }

    backtracing(0)
    return result
};

cpp 解法, 执行用时: 56 ms, 内存消耗: 19.4 MB, 提交时间: 2022-12-12 14:48:17

class Solution {
public:
    vector<int> temp; 
    vector<vector<int>> ans;

    void dfs(int cur, int last, vector<int>& nums) {
        if (cur == nums.size()) {
            if (temp.size() >= 2) {
                ans.push_back(temp);
            }
            return;
        }
        if (nums[cur] >= last) {
            temp.push_back(nums[cur]);
            dfs(cur + 1, nums[cur], nums);
            temp.pop_back();
        }
        if (nums[cur] != last) {
            dfs(cur + 1, last, nums);
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        dfs(0, INT_MIN, nums);
        return ans;
    }
};

java 解法, 执行用时: 2 ms, 内存消耗: 47.5 MB, 提交时间: 2022-12-12 14:48:02

class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(0, Integer.MIN_VALUE, nums);
        return ans;
    }

    public void dfs(int cur, int last, int[] nums) {
        if (cur == nums.length) {
            if (temp.size() >= 2) {
                ans.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        if (nums[cur] >= last) {
            temp.add(nums[cur]);
            dfs(cur + 1, nums[cur], nums);
            temp.remove(temp.size() - 1);
        }
        if (nums[cur] != last) {
            dfs(cur + 1, last, nums);
        }
    }
}

java 解法, 执行用时: 98 ms, 内存消耗: 49.2 MB, 提交时间: 2022-12-12 14:45:14

// 二进制枚举 + hash
class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Set<Integer> set = new HashSet<Integer>();
    int n;

    public List<List<Integer>> findSubsequences(int[] nums) {
        n = nums.length;
        for (int i = 0; i < (1 << n); ++i) {
            findSubsequences(i, nums);
            int hashValue = getHash(263, (int) 1E9 + 7);
            if (check() && !set.contains(hashValue)) {
                ans.add(new ArrayList<Integer>(temp));
                set.add(hashValue);
            }
        }
        return ans;
    }

    public void findSubsequences(int mask, int[] nums) {
        temp.clear();
        for (int i = 0; i < n; ++i) {
            if ((mask & 1) != 0) {
                temp.add(nums[i]);
            }
            mask >>= 1;
        }
    }

    public int getHash(int base, int mod) {
        int hashValue = 0;
        for (int x : temp) {
            hashValue = hashValue * base % mod + (x + 101);
            hashValue %= mod;
        }
        return hashValue;
    }

    public boolean check() {
        for (int i = 1; i < temp.size(); ++i) {
            if (temp.get(i) < temp.get(i - 1)) {
                return false;
            }
        }
        return temp.size() >= 2;
    }
}

上一题

下一题

详情