491. Non-decreasing Subsequences

leetcode medium

#array#backtracking#csharp#hash-table#leetcode#medium#recursion#search

Task

Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке.

Пример:

Input: nums = [4,6,7,7]

Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

C# solution

matched/original

public class Solution {
    public IList<IList<int>> FindSubsequences(int[] nums) {
        var result = new HashSet<IList<int>>();
        var sequence = new List<int>();
        Backtrack(nums, 0, sequence, result);
        return result.ToList();
    }
    private void Backtrack(int[] nums, int index, List<int> sequence, HashSet<IList<int>> result) {
        if (index == nums.Length) {
            if (sequence.Count >= 2) {
                result.Add(new List<int>(sequence));
            }
            return;
        }
        if (sequence.Count == 0 || sequence[sequence.Count - 1] <= nums[index]) {
            sequence.Add(nums[index]);
            Backtrack(nums, index + 1, sequence, result);
            sequence.RemoveAt(sequence.Count - 1);
        }
        Backtrack(nums, index + 1, sequence, result);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<int>> FindSubsequences(vector<int>& nums) {
        var result = new HashSet<vector<int>>();
        var sequence = new List<int>();
        Backtrack(nums, 0, sequence, result);
        return result.ToList();
    }
    private void Backtrack(vector<int>& nums, int index, List<int> sequence, HashSet<vector<int>> result) {
        if (index == nums.size()) {
            if (sequence.size() >= 2) {
                result.push_back(new List<int>(sequence));
            }
            return;
        }
        if (sequence.size() == 0 || sequence[sequence.size() - 1] <= nums[index]) {
            sequence.push_back(nums[index]);
            Backtrack(nums, index + 1, sequence, result);
            sequence.RemoveAt(sequence.size() - 1);
        }
        Backtrack(nums, index + 1, sequence, result);
    }
}

Java solution

matched/original

class Solution {
    private void backtrack(int[] nums, int index, List<Integer> sequence,
            Set<List<Integer>> result) {
        if (index == nums.length) {
            if (sequence.size() >= 2) {
                result.add(new ArrayList<>(sequence));
            }
            return;
        }
        if (sequence.isEmpty() ||
                sequence.get(sequence.size() - 1) <= nums[index]) {
            sequence.add(nums[index]);
            backtrack(nums, index + 1, sequence, result);
            sequence.remove(sequence.size() - 1);
        }
        backtrack(nums, index + 1, sequence, result);
    }

    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        List<Integer> sequence = new ArrayList<Integer>();
        backtrack(nums, 0, sequence, result);
        return new ArrayList(result);
    }
}

JavaScript solution

matched/original

var findSubsequences = function(nums) {
    const result = new Set();
    const sequence = [];
    backtrack(nums, 0, sequence, result);
    return Array.from(result).map(JSON.parse);
};

function backtrack(nums, index, sequence, result) {
    if (index === nums.length) {
        if (sequence.length >= 2) {
            result.add(JSON.stringify(sequence));
        }
        return;
    }
    if (sequence.length === 0 || sequence[sequence.length - 1] <= nums[index]) {
        sequence.push(nums[index]);
        backtrack(nums, index + 1, sequence, result);
        sequence.pop();
    }
    backtrack(nums, index + 1, sequence, result);
}

Python solution

matched/original

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = set()
        sequence = []
        self.backtrack(nums, 0, sequence, result)
        return list(result)

    def backtrack(self, nums, index, sequence, result):
        if index == len(nums):
            if len(sequence) >= 2:
                result.add(tuple(sequence))
            return
        if not sequence or sequence[-1] <= nums[index]:
            sequence.append(nums[index])
            self.backtrack(nums, index + 1, sequence, result)
            sequence.pop()
        self.backtrack(nums, index + 1, sequence, result)

Go solution

matched/original

func findSubsequences(nums []int) [][]int {
    result := make(map[string][]int)
    sequence := []int{}
    backtrack(nums, 0, &sequence, result)
    res := [][]int{}
    for _, v := range result {
        res = append(res, v)
    }
    return res
}

func backtrack(nums []int, index int, sequence *[]int, result map[string][]int) {
    if index == len(nums) {
        if len(*sequence) >= 2 {
            key := fmt.Sprintf("%v", *sequence)
            result[key] = append([]int(nil), *sequence...)
        }
        return
    }
    if len(*sequence) == 0 || (*sequence)[len(*sequence)-1] <= nums[index] {
        *sequence = append(*sequence, nums[index])
        backtrack(nums, index+1, sequence, result)
        *sequence = (*sequence)[:len(*sequence)-1]
    }
    backtrack(nums, index+1, sequence, result)
}

Explanation

Algorithm

Инициализация и запуск функции обратного отслеживания

Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0.

Функция обратного отслеживания

Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента.

Возврат результата

После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его.

😎