C++ O(2^N) dfs and using vector


  • 0
    K
    class Solution {
    public:
    	vector<vector<int>> ret;
    	vector<int> prev;
    	vector<int> subSeq;
    	void dfs(vector<int>& nums, int idx)
    	{
    		if(subSeq.size() > 1)ret.push_back(subSeq);
    		for (int i = idx; i < nums.size(); i++)
    		{
    			//1. The first condition is about duplication.
    			//if prev[i] is in the avail range[idx, nums.size()), i should be ignored
    			//2. other conditions are about increasement. 
    			if ((idx > prev[i]) && (subSeq.size() == 0 || subSeq[subSeq.size() - 1] <= nums[i]))
    			{
    				subSeq.push_back(nums[i]);
    				dfs(nums, i + 1);
    				subSeq.pop_back();
    			}
    		}
    	}
    	vector<vector<int>> findSubsequences(vector<int>& nums) {
    		int subSeq = 0;
    		prev = vector<int>(nums.size(), -1);
    		vector<int> last(201,-1);
    		// previous position of what has same number with num[i] is prev[i]
    		for (int i = 0; i < nums.size(); i++)last[nums[i] + 100] = -1;
    		for (int i = 0 ; i < nums.size() ; i++)
    		{
    			prev[i] = last[nums[i] + 100];
    			last[nums[i] + 100] = i;
    		}
    		dfs(nums,  0);
    		return ret;
    	}
    };
    

Log in to reply
 

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