Two method using c++(backtracking and )


  • 0
    • 1
      vector<vector<int> > findSubsequences(vector<int>& nums) {
      vector<vector<int> > result;
      vector<vector<int> > return_result;
      vector<int> v;
      int *splitSize = new int[nums.size()]; // 重复元素分割size
      result.push_back(v);

      for (unsigned int i = 0; i < nums.size(); i++) {
      	int start = 0;
      	for (unsigned int n = 0; n < i; n++) {
      		if (nums[n] == nums[i]) {
      			start = splitSize[n];
      		}
      	}
      	unsigned int size = result.size();
      	for (unsigned int j = start; j < size; j++) {
      		v = result[j];
      		if (v.size() == 0 || v[v.size() - 1] <= nums[i]) {
      			v.push_back(nums[i]);
      			result.push_back(v);
      			if (v.size() >= 2) {
      				return_result.push_back(v);
      			}
      		}
      	}
      	splitSize[i] = size;
      }
      return return_result;
      

      }

    • 2
      vector<vector<int> > findSubsequences(vector<int>& nums) {
      vector<vector<int> > result;
      vector<int> tmp;
      findSubsequences(nums, result, tmp, 0);
      return result;
      }

      void findSubsequences(vector<int>& nums, vector<vector<int> >& res,
      vector<int>& tmp, int start) {
      if (start >= nums.size()) {
      return;
      }
      for (int i = start; i < nums.size(); i++) {
      bool isReapeted = false;
      for (int j = start; j < i; j++) {
      //重复元素的判断
      if (nums[j] == nums[i]) {
      isReapeted = true;
      }
      }
      if ((start == 0 || (nums[i] >= tmp[tmp.size() - 1]))
      && (!isReapeted)) {
      // 注意第一个元素也要判断重复
      tmp.push_back(nums[i]);

      		if (tmp.size() > 1) {
      			res.push_back(tmp);
      		}
      		findSubsequences(nums, res, tmp, i + 1);
      		tmp.pop_back();
      	}
      }
      

      }


Log in to reply
 

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