1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int sz = nums.size();
        
        vector<int> vec = nums;
        sort(vec.begin(),vec.end());
        
        vector<int> hash(101); 
        for(int i = sz-1;i>=0;i--) {
            
            hash[vec[i]] = i; 
        }
        vector<int> result;
        for(int i = 0;i<sz;i++) {
            result.push_back(hash[nums[i]]);
        }
        return result;

    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool validMountainArray(vector<int>& A) {
        if (A.size() < 3) return false;
        int left = 0;
        int right = A.size() - 1;

        
        while (left < A.size() - 1 && A[left] < A[left + 1]) left++;

        
        while (right > 0 && A[right] < A[right - 1]) right--;

        
        if (left == right && left != 0 && right != A.size() - 1) return true;
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        int count[2001] = {0}; 
        for (int i = 0; i < arr.size(); i++) {
            count[arr[i] + 1000]++;
        }
        bool fre[1001] = {false}; 
        for (int i = 0; i <= 2000; i++) {
            if (count[i]) {
                if (fre[count[i]] == false) fre[count[i]] = true;
                else return false;
            }
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        
        int sz = nums.size();
        int ptr{};
        for(int i = 0;i<sz;i++) {
            
            if(nums[i]!=0) {
                swap(nums[ptr],nums[i]);
                ptr++;
            }
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        
        
        int sz = nums.size();
        int slowIndex{};
        for(int i = 0;i<sz;i++) {
            if(nums[i] != val) {
                swap(nums[i],nums[slowIndex]);
                slowIndex++;
            }
        }
        return slowIndex;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        
        int sz = nums.size();
        k = k%sz;
        
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        
        int sz = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        vector<int> prefixSum(sz);
        
        for (int i = 1; i < sz; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        for (int i = 0; i < sz; i++) {
            
            if(prefixSum[i]*2 == sum-nums[i]) {
                return i;
            }
        }
        return -1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
public:
    int find_first_index(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int leftIdx = -2;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            
            if (target > num) {
                
                left = mid + 1;
            } else {
                right = mid - 1;
                leftIdx = right;
            }
        }
        return leftIdx;
    }
    int find_last_index(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int rightIdx = -2;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            
            if (target >= num) {
                
                left = mid + 1;
                rightIdx = left;
            } else {
                right = mid - 1;
            }
        }
        return rightIdx;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int l = find_first_index(nums, target);
        int r = find_last_index(nums, target);
        if (l == -2 || r == -2) {
            return {-1, -1};
        }
        if (r - l > 1) {
            return {l + 1, r - 1};
        }
        return {-1, -1};
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head) {
            return nullptr;
        }
        ListNode* dummy = new ListNode(0,head);
        ListNode* cur = head;
        ListNode* prev = dummy;
        while(cur && cur->next) {
            ListNode* next_node = cur->next;
            cur->next = next_node->next;
            next_node->next = cur;
            prev->next = next_node;

            
            prev = cur;
            cur = cur->next;
        }
        return dummy->next;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    ListNode* reverseList(ListNode* node) {
        ListNode* prev = nullptr;
        while(node) {
            ListNode* next_node = node->next;
            node->next = prev;
            prev = node;
            node = next_node;
        }
        return prev;
    }
    bool isPalindrome(ListNode* head) {
         
         if(!head) {
            return true;
         }
         ListNode* cur = head;
         ListNode* slowPtr = head,*fastPtr = head; 
         while(fastPtr && fastPtr->next) {
            fastPtr = fastPtr->next->next;
            slowPtr = slowPtr->next;
         }
         
         ListNode* r = reverseList(slowPtr);
        while(r && cur) {
            if(r->val != cur->val) {
                return false;
            }
            r = r->next;
            cur = cur->next;
        }
        return true;
    }
};

1

L0 → L1 → … → Ln - 1 → Ln

1

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {
public:
    ListNode* getMiddle(ListNode* node) {
        if (!node) {
            return nullptr;
        }
        ListNode *slowPtr = node, *fastPtr = node;
        while (fastPtr && fastPtr->next && fastPtr->next->next) {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }
        ListNode* result = slowPtr->next;
        slowPtr->next = nullptr;
        return result;
    }
    ListNode* reverse(ListNode* node) {
        if (node == nullptr) {
            return nullptr;
        }
        ListNode* prev = nullptr;
        while (node) {
            ListNode* next_node = node->next;
            node->next = prev;
            prev = node;
            node = next_node;
        }
        return prev;
    }
    void reorderList(ListNode* head) {
        
        ListNode* middleNode = getMiddle(head);
        
        ListNode* rlist = reverse(middleNode);
        
        ListNode* cur = head;
        ListNode* llist = head->next;
        int cnt{1};
        while (rlist && llist) {
            if (cnt % 2) {
                cur->next = rlist;
                rlist = rlist->next;
            } else {
                cur->next = llist;
                llist = llist->next;
            }
            cnt++;
            cur = cur->next;
        }
        if (llist) {
            cur->next = llist;
        }
        if (rlist) {
            cur->next = rlist;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) return true;
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head) {
            return nullptr;
        }
        ListNode* slowptr = head;
        ListNode* fastptr = head;

        while (fastptr && fastptr->next) {
            slowptr = slowptr->next;
            fastptr = fastptr->next->next;
            if (slowptr == fastptr) {
                ListNode* cur = head;
                
                while (cur != slowptr) {
                    cur = cur->next;
                    slowptr = slowptr->next;
                }
                return cur;
            }
        }
        return nullptr;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

  class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int sz = cardPoints.size();
        int t = sz - k;
        int sum_val = accumulate(cardPoints.begin(), cardPoints.end(), 0);
        int min_val{};
          string s;
        for (int i = 0; i < t; i++) {
            min_val += cardPoints[i];
        }
        int res = min_val;
        for (int i = t; i < sz; i++) {
            min_val += cardPoints[i] - cardPoints[i - t];
            res = min(res, min_val);
        }
      
        return sum_val-res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sz = nums.size();
        int sum_val = accumulate(nums.begin(), nums.end(), 0);
        int target = sum_val - x;
        if (target == 0) {
            return sz;
        }
        
        int val{};
        int i{};
        int ops = -1;
        for (int j = 0; j < sz; j++) {
            val += nums[j];
            if (val > target) {
                while (i < j && val > target) {
                    val -= nums[i];
                    i++;
                }
            }
            if (val == target) {
                ops = max(ops, j - i + 1);
            }
        }
        if (ops == -1) {
            return -1;
        } else {
            return sz - ops;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sz = nums.size();
        int sum_val = accumulate(nums.begin(), nums.end(), 0);
        if (sum_val < x) {
            return -1;
        }
        int left{}, right{};
        
        
        int ans{INT_MAX};
        while (right < sz) {
            sum_val -= nums[right];
            while (sum_val < x) {
                sum_val += nums[left];
                left++;
            }
            if (sum_val == x) {
                ans = min(ans, sz - (right - left + 1));
            }
            right++;
        }
        if (ans == INT_MAX) {
            return -1;
        } else {
            return ans;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    int takeCharacters(string s, int k) {
        
        int sz = s.size();
        
        
        vector<int> cnt(3);
        for (auto& ch : s) {
            cnt[ch - 'a']++;
        }
        int ans{INT_MAX};
        if (cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) {
            ans = min(ans, sz);
        } else {
            return -1;
        }
        int left{}, right{};
        int l{};
        
        for (int r = 0; r < sz; r++) {
            
            cnt[s[r] - 'a']--;
            while (l < r && (cnt[0] < k || cnt[1] < k || cnt[2] < k)) {
                cnt[s[l] - 'a']++;
                l++;
            }
            if (cnt[0] >= k && cnt[1] >= k &&cnt[2] >= k) {
                ans = min(ans,  sz -(r-l+1));
            }
        }
        return ans;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> cnt(256);
        vector<bool> exists(256);
        int counts = t.size(); 
        for (auto& ch : t) {
            cnt[ch]++;
            exists[ch] = true;
        }
        int l{};
        int min_l{}, min_len{INT_MAX};
        
        for (int j = 0; j < s.size(); j++) {
            char ch = s[j];
            if (exists[ch]) {
                cnt[ch]--;
                
                if (cnt[ch] >= 0) {
                    counts--;
                }
                while (counts == 0) {
                    if (min_len > j - l + 1) {
                        min_l = l;
                        min_len = j - l + 1;
                    }
                    
                    if (exists[s[l]]) {
                        cnt[s[l]]++;
                        if (cnt[s[l]] > 0) {
                            counts++;
                        }
                    }
                    l++;
                }
            }
        }
        if (min_len == INT_MAX) {
            return "";
        } else {
            return s.substr(min_l, min_len);
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int characterReplacement(string s, int k) {
        
        int sz = s.size();
        int i{},j{};
        int max_cnt{};
        unordered_map<int,int> umap;
        int res{};
        while(j<sz) {
            umap[s[j]]++;
            max_cnt = max(max_cnt,umap[s[j]]);
            while(j-i+1>max_cnt+k) {
                umap[s[i]]--;
                i++;
            }
            res = max(res,j-i+1);
            j++;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0;
        int active_flips = 0; 

        
        for (int i = 0; i < n; ++i) {
            
            
            
            
            if (i >= k && nums[i - k] == 2) {
                active_flips--;
            }

            
            
            
            
            
            
            int current_state = nums[i]; 
            if (active_flips % 2 != 0) {
                current_state = 1 - nums[i]; 
            }

            
            if (current_state == 0) {
                
                if (i + k > n) {
                    return -1; 
                }

                
                ans++;
                active_flips++;
                
                
                
                
                nums[i] = 2; 
            }
        }

        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        
        
        
        
        sort(nums.begin(),nums.end());
        int right = nums.back() - nums.front();
        int left = 0;
        int ans{};
        while(left<=right) {
            int mid = (right-left)/2+left;
            
            int l{},r{};
            
            int cnt{};
            while(r<nums.size()) {
                while(l<nums.size() && nums[r]-nums[l]>mid){
                    l++;
                }
                cnt  += r-l; 
                r++;
            }
            if(cnt>=k) {
                ans = mid;
                right= mid-1;
            }else{
                left = mid+1;
            }

        }
        return ans;

    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        
        for(int i = 1;i<intervals.size();i++) {
            if(intervals[i][0]<intervals[i-1][1]) {
                return false;
            }
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int sz = intervals.size();
        vector<int> in(sz);
        vector<int> out(sz);
        for(int i = 0;i<sz;i++) {
            in[i] = intervals[i][0];
            out[i] = intervals[i][1];
        }
        sort(in.begin(),in.end());
        sort(out.begin(),out.end());
        int usedRooms{};
        int i{},j{};
        while(i<sz){
            if(in[i]>=out[j]) {
                
                j++;
            }else{
                usedRooms++;
            }
            i++;
        }
        return usedRooms;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int sz = intervals.size();
        vector<pair<int, int>> timestamps;
        for (auto& interval : intervals) {
            timestamps.emplace_back(interval[0], 1);
            timestamps.emplace_back(interval[1], -1);
        }
        sort(timestamps.begin(), timestamps.end());
        int maxRooms{};
        int res{};
        for (auto& p : timestamps) {
            maxRooms += p.second;
            res = max(res, maxRooms);
        }
        return res;
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int sz = trips.size();
        int max_to{INT_MIN};
        for(auto& trip:trips) {
            max_to = max(max_to,trip[2]);
        }
        vector<int> stages(1+max_to);
        for(auto& trip:trips) {
            stages[trip[1]] += trip[0];
            stages[trip[2]] -= trip[0];
        }
        int max_val{};
        for(auto n:stages) {
            max_val +=n;
            if(max_val>capacity) {
                return false;
            }
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
       sort(intervals.begin(),intervals.end());
       
       int sz = intervals.size();
       int result{};
       for(int i = 1;i<sz;i++) {
          if(intervals[i][0]<intervals[i-1][1]) {
            
            
            result++;
            intervals[i][1] = min(intervals[i-1][1],intervals[i][1]);
          }
       }
       return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
       sort(points.begin(),points.end());
       int n  = points.size();
       int r{1};
       for(int i =1;i<n;i++) {
            if(points[i][0]>points[i-1][1]) {
                r++;
            }else{
                points[i][1] = min(points[i-1][1],points[i][1]);
            }
       }
    return r;

    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> partitionLabels(string s) {
        
        
        vector<int> cnts(26);
        for (int i = 0; i < s.size(); i++) {
            cnts[s[i] - 'a'] = i;
        }
        vector<int> r;
        int start{};
        int maxPos{};
        for (int i = 0; i < s.size(); i++) {
            maxPos = max(maxPos, cnts[s[i] - 'a']);
            if (i == maxPos) {
                
                r.push_back(i - start + 1);
                start = i+1;
            }
        }
        return r;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        vector<vector<int>> r;
        r.push_back(intervals[0]);
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] <= r.back()[1]) {
                
                
                r.back()[1] = max(intervals[i][1],  r.back()[1]);
            } else {
                r.push_back(intervals[i]);
            }
        }
        return r;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string ns = to_string(n);
        int sz = ns.size();
        int flag{sz};
        for (int i = sz - 2; i >= 0; i--) {
            if (ns[i] > ns[i + 1]) {
                
                ns[i] -= 1;
                flag = i + 1;
            }
        }
        for (int i = flag; i < sz; i++) {
            ns[i] = '9';
        }
        return stoi(ns);
    }
};

1
2
3
4
5

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { 
            path.push_back(i); 
            backtracking(n, k, i + 1);
            path.pop_back(); 
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    void backtrace(vector<int>& candidates, int targetSum,
                   vector<vector<int>>& result, vector<int>& path, int startIdx,
                   int sumVal) {
        
        if (sumVal > targetSum) {
            return;
        }
        if (sumVal == targetSum) {
            result.push_back(path);
            return;
        }
        for (int i = startIdx;
             
             i < candidates.size() && sumVal + candidates[i] <= targetSum;
             i++) {
            path.push_back(candidates[i]);
            
            backtrace(candidates, targetSum, result, path, i,
                      sumVal + candidates[i]);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        
        vector<vector<int>> result;
        vector<int> path;
        backtrace(candidates, target, result, path, 0, 0);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    void backtrace(vector<int>& candidates, int target,
                   vector<int>& path, vector<vector<int>>& result, int sumVal,int idx,vector<bool>& isUsed) {
        
        if (sumVal > target) {
            return;
        }
        if(sumVal == target) {
            result.push_back(path);
            return;
        }
        for(int i = idx;i<candidates.size() && candidates[i]+sumVal<=target;i++) {
            if(i>0 && candidates[i] == candidates[i-1] && isUsed[i-1] == false) {
                
                continue;
            }
            isUsed[i] = true;
            path.push_back(candidates[i]);
            backtrace(candidates,target,path,result,sumVal+candidates[i],i+1,isUsed);
            path.pop_back();
            isUsed[i] = false;
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        
        vector<int> path;
        vector<vector<int>> result;
        sort(candidates.begin(), candidates.end());
        vector<bool> isUsed(candidates.size());
        backtrace(candidates, target, path, result,0,0,isUsed);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    void backtrace(vector<int>& candidates, int target,
                   vector<int>& path, vector<vector<int>>& result, int sumVal,int idx) {
        
        if (sumVal > target) {
            return;
        }
        if(sumVal == target) {
            result.push_back(path);
            return;
        }
        for(int i = idx;i<candidates.size() && candidates[i]+sumVal<=target;i++) {
            if(i>idx && candidates[i] == candidates[i-1] ) {
                
                continue;
            }
            isUsed[i] = true;
            path.push_back(candidates[i]);
            backtrace(candidates,target,path,result,sumVal+candidates[i],i+1);
            path.pop_back();
            isUsed[i] = false;
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        
        vector<int> path;
        vector<vector<int>> result;
        sort(candidates.begin(), candidates.end());
        vector<bool> isUsed(candidates.size());
        backtrace(candidates, target, path, result,0,0);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    void backtrace(int k, int n, int idx, vector<int>& path,
                   vector<vector<int>>& result, int sumVal) {
        if (sumVal > n) {
            return;
        }
        if (k == path.size()) {
            
            if (sumVal == n) {
                
                result.push_back(path);
            }
            
            return;
        }

        for (int i = idx; i <= 9-(k-path.size())+1; i++) {
            path.push_back(i);
            backtrace(k, n, i + 1, path, result, sumVal + i);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> path;
        vector<vector<int>> result;
        backtrace(k, n, 1, path, result, 0);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    bool isPalin(string&s,int i,int j) {
        int l = i,r=j;
        while(l<r) {
            if(s[l]!=s[r]) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
    void backtrace(string& s,vector<string>& path,vector<vector<string>>& result,int startPos) {
        
        if(startPos == s.size()) {
            result.push_back(path);
            return;
        }
        for(int i = startPos;i<s.size();++i) {
             
             
             bool isValid = isPalin(s,st  artPos,i);
             if(isValid) {
                path.push_back(s.substr(startPos,i-startPos+1));
                backtrace(s,path,result,i+1);
                path.pop_back();
             }
        } 
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;
        backtrace(s,path,result,0);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
private:
    vector<vector<string>> result;
    vector<string> path; 
    vector<vector<bool>> isPalindrome; 
    void backtracking (const string& s, int startIndex) {
        
        if (startIndex >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isPalindrome[startIndex][i]) {   
                
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            } else {                                
                continue;
            }
            backtracking(s, i + 1); 
            path.pop_back(); 
        }
    }
    void computePalindrome(const string& s) {
        
        isPalindrome.resize(s.size(), vector<bool>(s.size(), false)); 
        for (int i = s.size() - 1; i >= 0; i--) { 
            
            for (int j = i; j < s.size(); j++) {
                if (j == i) {isPalindrome[i][j] = true;}
                else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);}
                else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);}
            }
        }
    }
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        computePalindrome(s);
        backtracking(s, 0);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {
public:
    bool isValidIp(string& s, int startPos, int endPos) {
        
        int len = endPos - startPos + 1;
        if (len > 3 || len == 0) {
            return false;
        }
        if (len > 1 && s[startPos] == '0') {
            return false;
        }
        int ipNum{};
        for (int i = startPos; i <= endPos; i++) {
            ipNum = ipNum * 10 + (s[i] - '0');
            if (ipNum > 255) {
                return false;
            }
        }
        if (ipNum >= 0 && ipNum <= 255) {
            return true;
        }
        return false;
    }

    
    void backtrace(string& s, vector<string>& result, int startPos,
                   int pointNum) {
        
        if (pointNum == 3) {
            if (isValidIp(s, startPos, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startPos; i < s.size(); i++) {
            
            if (isValidIp(s, startPos, i)) {
                
                s.insert(s.begin() + i + 1, '.');
                backtrace(s, result, i + 2, pointNum + 1);
                s.erase(i + 1, 1);
            } else {
                
                break;
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        if (s.size() < 4 || s.size() > 12) {
            return {};
        }
        backtrace(s, result, 0, 0);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    void backtrace(vector<int>& nums, int startIdx, vector<vector<int>>& result,
                   vector<int>& path) {
        
        
        result.push_back(path);
        for(int i = startIdx;i<nums.size();i++) {
            path.push_back(nums[i]);
            backtrace(nums,i+1,result,path);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        backtrace(nums,0,result,path);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    void backtrace(vector<int>& nums,int startIndex,vector<int>& path,vector<vector<int>>& result) {
        
        result.push_back(path);
        for(int i = startIndex;i<nums.size();i++) {
            if(i>startIndex && nums[i] == nums[i-1]) {
                
                continue;
            }
            path.push_back(nums[i]);
            backtrace(nums,i+1,path,result);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int> path;
        vector<vector<int>> result;
        backtrace(nums,0,path,result);
        return result;
    }   
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    
    void backtrace(vector<int>& nums, vector<int>& path,
                   vector<vector<int>>& result, int startPos ) {
        
        if (path.size() >= 2) {
            result.push_back(path);
        }
        vector<int> used(201);
        for (int i = startPos; i < nums.size(); i++) {
            if (used[nums[i]+100]) {
                continue;
            }
            if (path.empty() || nums[i] >= path.back()) {
                path.push_back(nums[i]);
                
                used[nums[i]+100] = true;
                backtrace(nums, path, result, i + 1);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(nums.size());
        backtrace(nums, path,result, 0);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    
    void backtrace(vector<int>& nums,vector<int>& path, vector<vector<int>>& result,
                   vector<bool>& isUsed) {
        if(nums.size() == path.size()) {
            result.push_back(path);
            return;
        }
        for(int i = 0;i<nums.size();i++) {
            if(isUsed[i]) {
                continue;
            }
            isUsed[i] = true;
            path.push_back(nums[i]);
            backtrace(nums,path,result,isUsed);
            path.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        
        int n = nums.size();
        vector<int> path ;
        vector<vector<int>> result;
        vector<bool> isUsed(n);
        backtrace(nums, path, result, isUsed);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    void backtrace(vector<int>& nums,vector<int>& path,vector<vector<int>>& result,vector<bool>& isUsed) {
        if(path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++) {
               
            
            
            if(i>0 &&nums[i] == nums[i-1] && isUsed[i-1]==false) {
                continue;
            }
             
            if(isUsed[i]) {
                continue;
            }
            path.push_back(nums[i]);
            isUsed[i] = true;
            backtrace(nums,path,result,isUsed);
            path.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        sort(nums.begin(),nums.end());
        vector<bool> isUsed(nums.size());
        backtrace(nums,path,result,isUsed);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
private:
vector<vector<string>> result;


void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { 
            chessboard[row][col] = 'Q'; 
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; 
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    
    for (int i = 0; i < row; i++) { 
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52