Sharing my very neat C++ back tracking solution


  • 0
    B

    Key is to use a set to track which numbers are used.

    class Solution {
    public:
        void backtracking(vector<int>& nums, vector<vector<int>>& ret, vector<int> run, int index) {
            if(run.size()>1) ret.push_back(run);
            unordered_set<int> check;
            for(int k = index; k<nums.size(); k++) {
                if((run.empty() || run.back()<=nums[k]) && check.find(nums[k])==check.end()) {
                    run.push_back(nums[k]);
                    backtracking(nums, ret, run, k+1);
                    run.pop_back();
                    check.insert(nums[k]);
                }
            }
            return;
        }
        vector<vector<int>> findSubsequences(vector<int>& nums) {
            vector<vector<int>> ret;
            if(nums.size()<2) return ret;
            backtracking(nums, ret, vector<int>{}, 0);
            return ret;
        }
    };
    

Log in to reply
 

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