Today I have done leetcode's January LeetCoding Challenge with cpp.

January LeetCoding Challenge 20

Description

Non-decreasing Subsequences

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

Example 1:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

Example 2:

Input: nums = [4,4,3,2,1]
Output: [[4,4]]

Constraints:

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

Solution

constexpr int pop_count(int x) {
  const int m1  = 0X55555555;
  const int m2  = 0X33333333;
  const int m4  = 0X0F0F0F0F;
  const int m8  = 0X00FF00FF;
  const int m16 = 0X0000FFFF;
  x = (x &  m1) + ((x >>  1) &  m1);
  x = (x &  m2) + ((x >>  2) &  m2);
  x = (x &  m4) + ((x >>  4) &  m4);
  x = (x &  m8) + ((x >>  8) &  m8);
  x = (x & m16) + ((x >> 16) & m16);
  return x;
}
class Solution {
  vector<int> getSubsequence(int mask, const vector<int> &array) {
    vector<int> result;
    for(int i = 0; i < array.size(); ++i) {
      if((1 << i) & mask) {
        result.push_back(array[i]);
      }
    }
    return result;
  }
  bool validSubsequence(int mask, const vector<int> &array) {
    int last = -101;
    for(int i = 0; i < array.size(); ++i) {
      if(!((1 << i) & mask)) continue;
      if(array[i] < last) return false;
      last = array[i];
    }
    return true;
  }
public:
  vector<vector<int>> findSubsequences(vector<int>& nums) {
    int bits = nums.size();
    int maxMask = 1 << bits;

    vector<vector<int>> answer;
    for(int i = 1; i < maxMask; ++i) {
      if(pop_count(i) < 2) continue;
      if(!validSubsequence(i, nums)) continue;
      answer.emplace_back(getSubsequence(i, nums));
    }

    sort(answer.begin(), answer.end());
    answer.resize(unique(answer.begin(), answer.end()) - answer.begin());
    return answer;
  }
};

// Accepted
// 58/58 cases passed (162 ms)
// Your runtime beats 24.96 % of cpp submissions
// Your memory usage beats 33.17 % of cpp submissions (31.1 MB)