[LeetCode]Increasing Subsequences

很直观的backtracking类的题目，不需要多讲，要注意去重。关于去重的思路可以参考Permutations II。时间复杂度O(k)，k为IS(Increasing Subsequences)的数量，空间复杂度O(d)，d为最长的IS。代码如下：

	class Solution {
	public:
	vector<vector<int>> findSubsequences(vector<int>& nums) {
	vector<int> curr;
	vector<vector<int>> res;
	backtrack(res, nums, curr, 0);
	return res;
	}
	private:
	void backtrack(vector<vector<int>>& res, vector<int>& nums, vector<int>& curr, int idx)
	{
	if(curr.size() > 1)
	res.push_back(curr);
	if(idx == nums.size())
	return;
	unordered_set<int> used;
	for(int i = idx; i < nums.size(); ++i)
	{
	if((curr.empty() || nums[i] >= curr.back()) && used.find(nums[i]) == used.end())
	{
	used.insert(nums[i]);
	curr.push_back(nums[i]);
	backtrack(res, nums, curr, i + 1);
	curr.pop_back();
	}
	}
	}
	};

view raw Increasing Subsequences.cpp hosted with ❤ by GitHub