C++ dfs solution easy unserstanding using Map


  • 0
    W

    I use map to handle duplicates.
    I handle each size of subsequences from 2 to nums.size() separately.

    class Solution {
         void solve(vector<int>& nums, vector<vector<int> > &ans, vector<int> &tmp, int idx, int n) {
            if (n == 0) {
                ans.push_back(tmp);
                return;
            }
            if (idx >= nums.size()) {
                return;
            }
            map<int, int> myMap;
            for (int i = idx; i < nums.size(); i++) {
                if (myMap[nums[i]] > 0) {
                    continue;
                }
                if (tmp.size() > 0 && nums[i] < tmp.back()) {
                    continue;
                }
                myMap[nums[i]]++;
                tmp.push_back(nums[i]);
                solve (nums, ans, tmp, i + 1, n  - 1);
                tmp.pop_back();
            }
        }
    public:
        vector<vector<int>> findSubsequences(vector<int>& nums) {
            vector<vector<int>> ans;
            int n = nums.size();
            if (n < 2) {
                return ans;
            }
            vector<int> tmp;
            for (int i = 2; i <= n; i++) {
                solve(nums, ans, tmp, 0, i);
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.