Leetcode permutation and combination problem backtracking

46. A complete permutation without repeating elements

Give an array without duplicate numbers nums , Return all possible permutations . Do not limit the order of arrangement .Link

• Elements in different positions are exchanged and the results are traced
• In array 123 For example
  • The three numbers are respectively related to the 1 Exchange locations 1;2;3;
    • The last two numbers are respectively related to the 2 Exchange locations 12 13;21 23;32 31;
      • Last number and 3 Exchange locations 123 132;213 231;321 312;
      • [1] -> [12,13] -> [123, 132]
      • [2] -> [21, 23] -> [213, 231]
      • [3] -> [32, 31] -> [321, 312]
    • After the exchange, it will be restored , It's backtracking

class Solution {
    
public:
    vector<vector<int>> permute(vector<int>& nums) {
    
        vector<vector<int>> ret;
        backtracking(nums, 0, ret);
        return ret;
    }
    void backtracking(vector<int>& nums, int level, vector<vector<int>>& ret) {
    
        if (level == nums.size()) {
    
            ret.push_back(nums);
        }
        for (int i = level; i < nums.size(); i++) {
    
            swap(nums[i], nums[level]); //  With the first  level  A place exchange 
            backtracking(nums, level + 1, ret); //  Recursively swap the next position 
            swap(nums[i], nums[level]); //  The result of backtracking exchange 
        }
    }
};

47. Full permutation with repeating elements

Given a sequence that can contain repeating numbers nums , Returns all non repeating full permutations in any order .Link

• Elements in different positions are exchanged and the results are traced
• Prune the repeated elements that have been exchanged
• In array 1122 For example
• All elements are swapped with the first element , There are four situations [1, 1, 2, 2]; Produce repetition
  • Create a hash table to store the elements that have been exchanged with the first element , Before exchanging, check whether the element has been exchanged , If you have exchanged, you can directly continue; Otherwise, add the element to the hash table and exchange .
  • The element exchange at each subsequent position is handled as above , Store the elements that have been exchanged .

class Solution {
    
public:
    vector<vector<int>> ret;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    
        backTracking(nums, 0);
        return ret;
    }
    void backTracking(vector<int>& nums, int level) {
    
        int n = nums.size();
        if (level == n) {
    
            ret.push_back(nums);
            return;
        }
        set<int> st; //  Create a hash table to store the element values that have been exchanged 
        for (int i = level; i < n; i++) {
    
            if (st.find(nums[i]) != st.end()) continue; //  The current element has been linked to the  level  Elements have been exchanged , The exchange will repeat 
            st.insert(nums[i]); //  Put the exchanged element values into the hash table 
            swap(nums[i], nums[level]);
            backTracking(nums, level + 1); //  Swap elements of the next position 
            swap(nums[i], nums[level]);
        }
    }
};

784. All the letters are in uppercase and lowercase

Given a string s , By putting the string s Change the case of each letter in , We can get a new string . return All possible string sets . With In any order Return output .

• It is the same as the full arrangement of the above two numbers , But there is no need to exchange elements here , Just change the case
• Recursion starts with the first character
  • Keep the character constant recursion
  • Change character case recursively , Recursive end backtracking

class Solution {
    
public:
    int number;
    vector<string> ret;
    vector<string> letterCasePermutation(string s) {
    
        this->number = 'a' - 'A';
        backtracking(s, 0);
        return ret;
    }
    void backtracking(string& s, int i) {
    
        int n = s.size();
        if (i == n) {
    
            ret.push_back(s);
            return;
        }
        backtracking(s, i + 1); //  The current character does not change sign and recurses downward 
        //  Change the case of the current letter and recurse downward , Backtracking results 
        if (s[i] >= 'a' && s[i] <= 'z') {
    
            s[i] -= number;
            backtracking(s, i + 1);
            s[i] += number;
        }else if (s[i] >= 'A' && s[i] <= 'Z') {
    
            s[i] += number;
            backtracking(s, i + 1);
            s[i] -= number;
        }
    }
};

---

The above method will also recurse downward when encountering non letters , Recursion means that the current result is put on the stack , When the string length is too long , There may be a stack overflow , May adopt for Cycle through pruning , Reduce unnecessary recursion

• The current symbol is not a letter
  • Skip to the next symbol
• The current symbol is a letter
  • Recursion down without changing case
  • Change case, recurse down and backtrack
  • break sign out for loop , The remaining letters are processed recursively
• When the last character is not a letter , You may not be able to recursively save results , Because you need to judge the last character directly

---

• isalpha() Function can be used to determine whether the current character is a letter
• isdigit() Function can be used to determine whether the current character is a number
• s[i] ^= ’ '; The result of exclusive or between letters and spaces is equivalent to changing its case

class Solution {
    
public:
    vector<string> res;
    vector<string> letterCasePermutation(string s) {
    
        backtracking(s, 0);
        return res;
    }
    void backtracking(string& s, int index) {
    
        int n = s.size();
        if (index == n) {
    
            res.push_back(s);
            return;
        }
        for (int i = index; i < n; i++) {
    
            if (isalpha(s[i])) {
    
                backtracking(s, i + 1);
                s[i] ^= ' ';
                backtracking(s, i + 1);
                s[i] ^= ' ';
                break; //  The current letter recursion ends , direct  break
            }
            if (i == n - 1) {
    
                res.push_back(s); //  Non alphabetic processing of the last character 
            }
        }
    }
};