Leetcode Patterns & Related Problems
This page summarizes Leetcode problems by their core algorithmic patterns. Use it to quickly find related problems and practice similar techniques.
How to Use This Page
- Find a pattern you want to practice;
- Try all problems in that group to master the technique;
- Understand the similarities and differences between problems to deepen your understanding;
- Good reference for catorizing Leetcode problems;
DFS + Backtracking + DP + Bit Manipulation
How to select items to reach a specific value (similar to knapsack problems but it is a bit different):
Show C++ Solution
C++
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2) return false;
int target = sum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums) {
for (int i = target; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
};
Show C++ Solution
C++
class Solution {
public:
//dfs -> dfs + dp -> how to achieve dp -> bit as key
unordered_map<int, bool> m;
bool helper(vector<int>& nums, int k, int target, int cur, int visited){
if(m.count(visited))
return m[visited];
if(k == 0){
m[visited] = true;
return true;
}
if(cur > target){
m[visited] = false;
return false;
}
if(cur == target){
m[visited] = helper(nums, k-1, target, 0, visited);
return m[visited];
}
for(int i = 0; i < nums.size(); i++){
if((visited & (1 << i)) == 0 && target >= cur + nums[i]){
int last = visited;
visited |= 1 << i;
bool temp = helper(nums, k, target, cur+nums[i], visited);
if(temp){
m[visited] =true;
return true;
}
visited = last;
}
}
m[visited] = false;
return false;
}
bool makesquare(vector<int>& m) {
int val = accumulate(m.begin(), m.end(), 0);
if (val%4) return false;
return helper(m, 4, val/4, 0, 0);
}
};
Show C++ Solution
C++
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % k) return false;
int target = sum / k;
sort(nums.rbegin(), nums.rend());
vector<bool> used(nums.size(), false);
function<bool(int, int, int)> dfs = [&](int start, int curSum, int count) {
if (count == k) return true;
if (curSum == target) return dfs(0, 0, count + 1);
for (int i = start; i < nums.size(); ++i) {
if (!used[i] && curSum + nums[i] <= target) {
used[i] = true;
if (dfs(i + 1, curSum + nums[i], count)) return true;
used[i] = false;
}
}
return false;
};
return dfs(0, 0, 0);
}
};
Show C++ Solution
C++
class Solution {
public:
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= capacity; ++w) {
dp[i][w] = dp[i-1][w];
if (w >= weights[i-1])
dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
}
}
return dp[n][capacity];
}
};
Bit Manipulation
Show C++ Solution
C++
class Solution {
public:
int minFlips(int a, int b, int c) {
int flips = 0;
for (int i = 0; i < 32; ++i) {
int bitA = (a >> i) & 1;
int bitB = (b >> i) & 1;
int bitC = (c >> i) & 1;
if ((bitA | bitB) != bitC) {
flips += bitC ? 1 : 2;
}
}
return flips;
}
};
Standard DP Problem
One dimensional or two dimensional or three dimensional DP problems:
Show C++ Solution
C++
class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
dp[i][j] = dp[i][j - 1] + 1;
for (int k = i; k < j; ++k) {
if (s[k] == s[j]) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1]);
}
}
}
}
return dp[0][n - 1];
}
};
DFS
Show C++ Solution
C++
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return buildBST(nums, 0, nums.size() - 1);
}
private:
TreeNode* buildBST(const vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildBST(nums, left, mid - 1);
root->right = buildBST(nums, mid + 1, right);
return root;
}
};
Show C++ Solution
C++
class Solution {
public:
bool isSubPath(ListNode* head, TreeNode* root) {
if (!root) return false;
return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
}
private:
bool dfs(ListNode* head, TreeNode* node) {
if (!head) return true;
if (!node) return false;
if (head->val != node->val) return false;
return dfs(head->next, node->left) || dfs(head->next, node->right);
}
};
Show C++ Solution
C++
class Solution {
public:
int helper(const unordered_map<int, vector<int>>& graph, int node, int parent, int& ans) {
int pre = -1, acc = 1;
bool same = true;
bool isLeaf = true;
for (int neighbor : graph.at(node)) {
if (neighbor == parent) continue;
isLeaf = false;
int temp = helper(graph, neighbor, node, ans);
if (pre == -1)
pre = temp;
else if (pre != temp)
same = false;
acc += temp;
}
if (isLeaf || same) ans++;
return acc;
}
int countGoodNodes(vector<vector<int>>& edges) {
unordered_map<int, vector<int>> graph;
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
int ans = 0;
helper(graph, 0, -1, ans);
return ans;
}
};
BFS
Show C++ Solution
C++
class Solution {
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
vector<vector<vector<bool>>> visited(m, vector<vector<bool>>(n, vector<bool>(k + 1, false)));
queue<tuple<int, int, int>> q; // (row, col, remaining k)
q.push({0, 0, k});
visited[0][0][k] = true;
int steps = 0;
vector<int> directions = {0, 1, 0, -1, 0};
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
auto [row, col, remK] = q.front();
q.pop();
if (row == m - 1 && col == n - 1) return steps;
for (int d = 0; d < 4; ++d) {
int newRow = row + directions[d];
int newCol = col + directions[d + 1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
int newRemK = remK - grid[newRow][newCol];
if (newRemK >= 0 && !visited[newRow][newCol][newRemK]) {
visited[newRow][newCol][newRemK] = true;
q.push({newRow, newCol, newRemK});
}
}
}
}
steps++;
}
return -1;
}
};
Union Find
Consider use DFS or BFS first, if not work, then use Union Find. Here just show Union Find solutions that can be resolved by DFS or BFS as well:
Show C++ Solution
C++
class Solution {
public:
int find(int x, vector<int>& parent) {
if (parent[x] != x) {
parent[x] = find(parent[x], parent);
}
return parent[x];
}
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < n - 1) return -1;
vector<int> parent(n);
for (int i = 0; i < n; ++i) parent[i] = i;
int components = n;
for (const auto& conn : connections) {
int rootA = find(conn[0], parent);
int rootB = find(conn[1], parent);
if (rootA != rootB) {
parent[rootA] = rootB;
components--;
}
}
return components - 1;
}
};
Linked List
Problems involving manipulation of linked lists, including traversal, modification, and insertion:
Show C++ Solution
C++
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* curr = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int sum = carry;
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
}
return dummy.next;
}
};
Show C++ Solution
C++
class Solution {
public:
ListNode* insertGreatestCommonDivisors(ListNode* head) {
ListNode* curr = head;
while (curr && curr->next) {
int gcd = __gcd(curr->val, curr->next->val);
ListNode* node = new ListNode(gcd);
node->next = curr->next;
curr->next = node;
curr = node->next;
}
return head;
}
};
Stack
Problems involving using stack data structure for solving problems:
Show C++ Solution
C++
class Solution {
public:
bool isValid(string s) {
string temp;
unordered_map<char, char> m = {{')', '('}, {']', '['}, {'}', '{'},};
for (auto c : s) {
if (!m.count(c)) temp+= c;
else {
if (temp.empty() || temp.back() != m[c]) return false;
temp.pop_back();
}
}
return temp.size() == 0;
}
};
Braintease + Thinking (Analysis) + Simulation
Problems involving creative problem solving, array manipulation, and simulating real-world processes:
Show C++ Solution
C++
class Solution {
public:
int getLastMoment(int n, vector<int>& left, vector<int>& right) {
int res = 0;
for (int x : left) res = max(res, x);
for (int x : right) res = max(res, n - x);
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
// Simulate the falling path of each ball
vector<int> findBall(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> res(n, 0);
for (int j = 0; j < n; ++j) {
int col = j;
for (int i = 0; i < m; ++i) {
int dir = grid[i][col];
col += dir;
if (col < 0 || col >= n || grid[i][col] != dir) {
col = -1;
break;
}
}
res[j] = col;
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int countPermutations(vector<int>& complexity) {
int n = complexity.size();
long long MOD = 1e9 + 7;
// Step 1: Verify if computer 0 is strictly the smallest.
// If any other computer has equal or lower complexity, it cannot be unlocked.
for (int i = 1; i < n; ++i) {
if (complexity[i] <= complexity[0]) {
return 0;
}
}
// Step 2: If computer 0 is the strict minimum, it can unlock everything.
// Any permutation of the remaining (n-1) computers is valid.
long long ans = 1;
for (int i = 1; i < n; ++i) {
ans = (ans * i) % MOD;
}
return (int)ans;
}
};
Math
Problems involving mathematical concepts:
Show C++ Solution
C++
string fractionAddition(string expression) {
istringstream in(expression);
int A = 0, B = 1, a, b;
char _;
while (in >> a >> _ >> b) {
A = A * b + a * B;
B *= b;
int g = abs(__gcd(A, B));
A /= g;
B /= g;
}
return to_string(A) + '/' + to_string(B);
}
Show C++ Solution
C++
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
long long res = 0, count = 0;
for (int num : nums) {
if (num == 0) {
count++;
res += count;
} else {
count = 0;
}
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int alternateDigitSum(int n) {
int sum = 0, sign = 1;
while (n > 0) {
sum += sign * (n % 10);
n /= 10;
sign *= -1;
}
return sum * (-sign);
}
};
Binary Tree or Binary Search Tree
Problems involving binary tree or binary search trees, mostly about recursion:
Show C++ Solution
C++
class Solution {
public:
void inorder(TreeNode* root, vector<int>& vals) {
if (!root) return;
inorder(root->left, vals);
vals.push_back(root->val);
inorder(root->right, vals);
}
vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
vector<int> vals;
inorder(root, vals);
vector<vector<int>> res;
for (int q : queries) {
auto it = lower_bound(vals.begin(), vals.end(), q);
int floor = -1, ceil = -1;
if (it != vals.end() && *it == q) {
floor = ceil = q;
} else {
if (it != vals.end()) ceil = *it;
if (it != vals.begin()) floor = *(prev(it));
}
res.push_back({floor, ceil});
}
return res;
}
};
Sorting - both O(n log n) and O(n)
Show C++ Solution
C++
class Solution {
public:
int sum = 0;
TreeNode* bstToGst(TreeNode* root) {
if (!root) return nullptr;
bstToGst(root->right);
sum += root->val;
root->val = sum;
bstToGst(root->left);
return root;
}
};
Show C++ Solution
C++
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int res = INT_MAX;
for (int i = 0; i <= nums.size() - k; ++i) {
res = min(res, nums[i + k - 1] - nums[i]);
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) {
unordered_set<string> pos(positive_feedback.begin(), positive_feedback.end());
unordered_set<string> neg(negative_feedback.begin(), negative_feedback.end());
vector<pair<int, int>> scores;
for (int i = 0; i < report.size(); ++i) {
int score = 0;
stringstream ss(report[i]);
string word;
while (ss >> word) {
if (pos.count(word)) score += 3;
else if (neg.count(word)) score -= 1;
}
scores.push_back({-score, student_id[i]});
}
sort(scores.begin(), scores.end());
vector<int> res;
for (int i = 0; i < k; ++i) {
res.push_back(scores[i].second);
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int maxProduct(int n)
{
int max1 = -1, max2 = -1;
while (n > 0) {
int digit = n % 10;
if (digit > max1) {
max2 = max1;
max1 = digit;
} else if (digit > max2) {
max2 = digit;
}
n /= 10;
}
return max1 * max2;
}
};
Binary Search
Show C++ Solution
C++
class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int n = mountainArr.length();
int left = 0, right = n - 1;
// Find peak index
while (left < right) {
int mid = left + (right - left) / 2;
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
int peak = left;
// Search in the ascending part
left = 0; right = peak;
while (left <= right) {
int mid = left + (right - left) / 2;
int val = mountainArr.get(mid);
if (val == target) return mid;
if (val < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// Search in the descending part
left = peak; right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int val = mountainArr.get(mid);
if (val == target) return mid;
if (val > target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};
Show C++ Solution
C++
class RangeFreqQuery {
unordered_map<int, vector<int>> indices;
public:
RangeFreqQuery(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i) {
indices[arr[i]].push_back(i);
}
}
int query(int left, int right, int value) {
if (!indices.count(value)) return 0;
const auto& vec = indices[value];
int l = lower_bound(vec.begin(), vec.end(), left) - vec.begin();
int r = upper_bound(vec.begin(), vec.end(), right) - vec.begin();
return r - l;
}
};
Hashing
Problems involving hashing and count frequencies of elements:
Show C++ Solution
C++
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (const string& s : strs) {
string key = s;
sort(key.begin(), key.end());
groups[key].push_back(s);
}
vector<vector<string>> res;
for (auto& p : groups) res.push_back(p.second);
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
unordered_map<string, vector<string>> groups;
for (const string& s : strings) {
string key;
for (int i = 1; i < s.size(); ++i) {
int diff = (s[i] - s[i-1] + 26) % 26;
key += to_string(diff) + ",";
}
groups[key].push_back(s);
}
vector<vector<string>> res;
for (auto& p : groups) res.push_back(p.second);
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int flipgame(vector<int>& fronts, vector<int>& backs) {
unordered_set<int> same;
for (int i = 0; i < fronts.size(); ++i) {
if (fronts[i] == backs[i]) {
same.insert(fronts[i]);
}
}
int res = INT_MAX;
for (int x : fronts) {
if (!same.count(x)) res = min(res, x);
}
for (int x : backs) {
if (!same.count(x)) res = min(res, x);
}
return res == INT_MAX ? 0 : res;
}
};
Show C++ Solution
C++
class Solution {
public:
vector<string> removeAnagrams(vector<string>& words) {
vector<string> res;
for (const string& w : words) {
if (res.empty() || !isAnagram(res.back(), w)) {
res.push_back(w);
}
}
return res;
}
bool isAnagram(const string& a, const string& b) {
if (a.size() != b.size()) return false;
vector<int> count(26, 0);
for (char c : a) count[c - 'a']++;
for (char c : b) count[c - 'a']--;
for (int c : count) if (c != 0) return false;
return true;
}
};
Show C++ Solution
C++
class Solution {
public:
int minimumLength(string s) {
unordered_map<char, int> c;
for (auto d : s)
c[d]++;
int ans = 0;
for (auto d : c)
if (d.second % 2 == 1)
ans++;
else
ans += 2;
return ans;
}
};
Show C++ Solution
C++
class Solution {
public:
int minOperations(vector<int>& nums, int k) {
if (*min_element(nums.begin(), nums.end()) < k)
return -1;
unordered_set<int> s(nums.begin(), nums.end());
return s.count(k) ? s.size() - 1 : s.size();
}
};
Greedy
Show C++ Solution
C++
// Solution 1: dynamic programming with greedy choice property:
// Solution 2: greedy + binary search
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int num : nums) {
auto it = lower_bound(dp.begin(), dp.end(), num);
if (it == dp.end()) {
dp.push_back(num);
} else {
*it = num;
}
}
return dp.size();
}
};
Show C++ Solution
C++
// This is similar to Question 300. Longest Increasing Subsequence
// but with non-decreasing sequence, so we use upper_bound instead of lower_bound
class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
vector<int> dp, res;
for (int obs : obstacles) {
auto it = upper_bound(dp.begin(), dp.end(), obs);
if (it == dp.end()) {
dp.push_back(obs);
res.push_back(dp.size());
} else {
*it = obs;
res.push_back(it - dp.begin() + 1);
}
}
return res;
}
};
Show C++ Solution
C++
class Solution {
public:
int minMoves(int target, int maxDoubles) {
int moves = 0;
while (target > 1 && maxDoubles > 0) {
if (target % 2 == 0) {
target /= 2;
maxDoubles--;
} else {
target -= 1;
}
moves++;
}
return moves + target - 1;
}
};
Show C++ Solution
C++
class Solution {
public:
long long maximumImportance(int n, vector<vector<int>>& roads) {
vector<int> degree(n, 0);
for (const auto& road : roads) {
degree[road[0]]++;
degree[road[1]]++;
}
sort(degree.begin(), degree.end());
long long res = 0;
for (int i = 0; i < n; ++i) {
res += 1LL * degree[i] * (i + 1);
}
return res;
}
};
Heap
Use heap to manage a dynamic set of elements, allowing for efficient retrieval of the largest or smallest elements, and design the data structure accordingly:
Show C++ Solution
C++
class MedianFinder {
priority_queue<int, vector<int>, greater<int>> pq1; // minimum
priority_queue<int, vector<int>, less<int>> pq2; // maximum
public:
MedianFinder() {
}
void addNum(int num) {
pq2.push(num);
pq1.push(pq2.top());
pq2.pop();
while(pq1.size() - pq2.size() > 1) {
int val = pq1.top();
pq1.pop();
pq2.push(val);
}
}
double findMedian() {
return pq1.size() == pq2.size()? ((double)pq1.top() + pq2.top()) / 2 : pq1.top();
}
};
Simple heap usage:
Show C++ Solution
C++
class Solution {
public:
long long maxKelements(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());
long long res = 0;
for (int i = 0; i < k; ++i) {
int top = pq.top(); pq.pop();
res += top;
pq.push((top + 2) / 3);
}
return res;
}
};
Segment Tree
Use segment tree to efficiently perform range queries and updates on an array, and design the data structure accordingly.
See problem list here.
Count Elements By Subarray
Show C++ Solution
C++
class Solution {
public:
int uniqueLetterString(string s) {
vector<vector<int>> pos(26);
for (int i = 0; i < 26; i++) pos[i].push_back(-1);
for (int i = 0; i < s.size(); i++) pos[s[i]-'A'].push_back(i);
for (int i = 0; i < 26; i++) pos[i].push_back(s.size());
int ans = 0;
for (int i = 0; i < 26; i++) {
for (int j = 1; j < pos[i].size() - 1; j++) {
ans += (pos[i][j] - pos[i][j-1]) * (pos[i][j+1] - pos[i][j]);
}
}
return ans;
}
};
Two Pointers
Show C++ Solution
C++
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0, valid = 0;
int start = 0, len = INT_MAX;
while (right < s.size()) {
char c = s[right];
right++;
if (need.count(c)) {
window[c]++;
if (window[c] == need[c]) valid++;
}
while (valid == need.size()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s[left];
left++;
if (need.count(d)) {
if (window[d] == need[d]) valid--;
window[d]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
Show C++ Solution
C++
class Solution {
public:
void reverseWords(vector<char>& s) {
// space O(1) is important for this question
reverse(s.begin(), s.end());
int index = 0;
while(index < s.size()) {
int b = index;
while(index < s.size() && s[index] != ' ') index++;
reverse(s.begin() + b, s.begin() + index);
index++;
}
}
};
Show C++ Solution
C++
class Solution {
public:
bool canMakeSubsequence(string str1, string str2) {
int i = 0, j = 0;
while (i < str1.size() && j < str2.size()) {
if (str1[i] == str2[j] || (str1[i] + 1 - 'a') % 26 + 'a' == str2[j]) {
j++;
}
i++;
}
return j == str2.size();
}
};
Simulation + Digital Counting and Finding
Show C++ Solution
C++
class Solution {
public:
char kthCharacter(long long k, const vector<int>& ops) {
const long long INF = (long long)4e18;
long long len = 1;
int n = ops.size(), i = 0, shift = 0;
while (i < n && len < k) { len = min(INF, len * 2); ++i; }
for (int j = i - 1; j >= 0; --j) {
long long half = len / 2;
if (k > half) {
k -= half;
if (ops[j] == 1) shift = (shift + 1) % 26;
}
len = half;
}
return char('a' + shift);
}
};
Geometry
Show C++ Solution
C++
class Solution {
public:
int numberOfPairs(vector<vector<int>>& p) {
sort(p.begin(), p.end(), [](vector<int>& a, vector<int>& b) {
if (a[0] == b[0])
return a[1] > b[1];
return a[0] < b[0];
});
int ans = 0;
for (int i = 0; i < p.size(); i++) {
int y = INT_MIN;
for (int j = i + 1; j < p.size(); j++) {
if (p[j][1] <= p[i][1] && y < p[j][1]) {
ans++;
y = p[j][1];
}
}
}
return ans;
}
};
Game Theory
Check the Problems List.
Show C++ Solution
C++
class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0;
}
};
Sliding Window
Show C++ Solution
C++
class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> ans;
string t = "123456789";
for (int len = 1; len <= t.size(); len++) {
for (int i = 0; i <= t.size() - len; i++) {
int v = stoi(t.substr(i, len));
if (v >= low && v <= high)
ans.push_back(v);
}
}
return ans;
}
};