[C++ code] Backtracking, subsets, combinations, full arrangements, deduplication – Code Random Notes

Title: Split palindrome string

Given a string s, please split s into some substrings so that each substring is a palindrome string. Returns all possible splitting options for s. Palindrome string is a string that reads the same when read forward or backward.
In the for (int i = startIndex; i < s.size(); i + + ) loop, we define the starting position startIndex, then [startIndex, i] is the substring to be intercepted . First, determine whether the substring is a palindrome. If it is a palindrome, add it to vector path. Path is used to record the cut palindrome substring.

class Solution {<!-- -->
public:
vector<vector<string>> res;
    vector<string> path;
    vector<vector<bool>> isP;
    void compP(const string & amp; s){<!-- -->
        isP.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){<!-- -->
                    isP[i][j]=true;
                }else if(j-i==1){<!-- -->
                    isP[i][j]=(s[i]==s[j]);
                }else{<!-- -->
                    isP[i][j]=(s[i]==s[j] & amp; & amp;isP[i + 1][j-1]);
                }
            }
        }
    }
    void track(const string & amp;s,int start){<!-- -->
        if(start>=s.size()){<!-- -->
            res.push_back(path);
            return;
        }
        for(int i=start;i<s.size();i + + ){<!-- -->
            if(isP[start][i]){<!-- -->
                string str=s.substr(start,i-start + 1);
                path.push_back(str);
            }else{<!-- -->
                continue;
            }
            track(s,i + 1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {<!-- -->
        res.clear();
        path.clear();
        compP(s);
        track(s,0);
        return res;
    }
};

Determine whether a string is a palindrome. You can use the double pointer method, one pointer from front to back, and one pointer from back to front. If the elements pointed to by the front and rear pointers are equal, it is a palindrome string.

bool isPalindrome(const string & amp; s, int start, int end) {<!-- -->
   for (int i = start, j = end; i < j; i + + , j--) {<!-- -->
       if (s[i] != s[j]) {<!-- -->
           return false;
       }
   }
   return true;
}

The isPalindrome function uses the double pointer method to determine whether the intercepted substring for a string s, given the starting subscript and the ending subscript, is a reply text. string. However, there is a certain amount of repeated calculations: for example, given the string "abcde", when it is known that "bcd" is not a palindrome string, there is no need to go to the double pointer. By operating "abcde", you can directly determine that it is not a reply text string.
Specifically, given a string s with length n, the necessary and sufficient condition for it to become a palindrome string is s[0] == s[ n-1] and s[1:n-1] is a reply text string. In the dynamic programming algorithm, wecan efficiently calculate in advance, for a string s, whether any of its substrings is a palindrome string, and then directly use it in our backtracking function Just query, eliminating the step of determining the movement of double pointers.

Title: Restoring IP Address

A valid IP address consists of exactly four integers, each between 0 and 255, without leading 0), integers are separated by '.'. For example: "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245" code>, "192.168.1.312" and "[email protected]" are invalid IP addresses.
Given a string s containing only numbers, representing an IP address, return all possible valid IP addresses that can be accessed by s< Insert '.' into /code> to form. You cannot reorder or delete any numbers in s. You can return answers in any order.



The cutting problem can be abstracted into a tree structure, as shown in the figure:





class Solution {<!-- -->
public:
    vector<string> res;
    bool isV(const string & amp;s,int start,int end){<!-- -->
        if(start>end){<!-- -->
            return false;
        }
        if(s[start]=='0' & amp; & amp; start!=end){<!-- -->// Numbers starting with 0 are illegal, except pure 0
            return false;
        }
        int num=0;
        for(int i=start;i<=end;i + + ){<!-- -->
            if(s[i]>'9'||s[i]<'0'){<!-- -->
                return false;
            }
            num =num*10 + (s[i]-'0');
            if(num>255){<!-- -->
                return false;
            }
        }
        return true;
    }
    void track(string & amp; s,int start,int pointnum){<!-- -->
        if(pointnum==3){<!-- -->
            if(isV(s,start,s.size()-1)){<!-- -->
                res.push_back(s);
            }
            return ;
        }

        for(int i=start;i<s.size();i + + ){<!-- -->
            if(isV(s,start,i)){<!-- -->
                s.insert(s.begin() + i + 1,'.');
                pointnum + + ;
                track(s,i + 2,pointnum);
                pointnum--;
                s.erase(s.begin() + i + 1);
            }else{<!-- -->
                break;
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {<!-- -->
        res.clear();
        if(s.size()<4||s.size()>12){<!-- -->
            return res;
        }
        track(s,0,0);
        return res;
    }
};



When making a recursive call, the start of the next level of recursion should start from i + 2 (because the separator . needs to be added to the string), and the number of recorded separators, pointnum, must be + 1. When backtracking, just delete the separator . you just added, and the pointnum should also be -1.


Topic: Subset


You are given an array of integers nums. The elements in the array are different from each other. Returns all possible subsets (power sets) of this array. The solution set cannot contain duplicate subsets. You can return solutions in any order.


If the subset problem, combination problem, and segmentation problem are all abstracted into a tree, then the combination problem and the segmentation problem are to collect the leaf nodes of the tree, while the subset problem is to find all the nodes of the tree ! In fact, subset is also a combination problem, because its set is unordered, and subset {1,2} is the same as subset {2,1}.


class Solution {<!-- -->
public:
    vector<vector<int>> res;
    vector<int> path;
    void track(vector<int> & amp;nums,int start){<!-- -->
        res.push_back(path);
        if(start>=nums.size()){<!-- -->
            return;
        }
        for(int i=start;i<nums.size();i + + ){<!-- -->
            path.push_back(nums[i]);
            track(nums,i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int> & amp; nums) {<!-- -->
        res.clear();
        path.clear();
        track(nums,0);
        return res;
    }
};



Title: Subset II


Given an integer array nums, which may contain duplicate elements, please return all possible subsets (power sets) of the array. The solution set cannot contain duplicate subsets. In the returned solution set, the subsets can be arranged in any order.






It can be seen from the figure that if you repeatedly pick 2 on the same tree level, you will filter it out, and you can repeatedly pick 2 on the same branch, because the set of elements on the same branch is the only subset!


class Solution {<!-- -->
public:
    vector<vector<int>> res;
    vector<int> path;
    void track(vector<int> & amp;nums,int start){<!-- -->
        res.push_back(path);
        unordered_set<int> uset;
        for(int i=start;i<nums.size();i + + ){<!-- -->
            if(uset.find(nums[i])!=uset.end()) continue;
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            track(nums,i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int> & amp; nums) {<!-- -->
        res.clear();
        path.clear();
        sort(nums.begin(),nums.end());
        track(nums,0);
        return res;
    }
};



Deduplication without using set


 void track2(vector<int> & amp; nums,int start,vector<bool> & amp; used){<!-- -->
        res.push_back(path);
        for(int i=start;i<nums.size();i + + ){<!-- -->
            if(i>0 & amp; & amp;nums[i]==nums[i-1] & amp; & amp;used[i-1]==false) continue;
            path.push_back(nums[i]);
            used[i]=true;
            track2(nums,i + 1,used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int> & amp; nums) {<!-- -->
        res.clear();
        path.clear();
        vector<bool> used(nums.size(),false);
        sort(nums.begin(),nums.end());
        track2(nums,0,used);
        return res;
    }



Title: Increasing Subsequence


Given an integer array nums, find and return all different increasing subsequences in the array. The increasing subsequences have at least two elements. You can return answers in any order. The array may contain repeated elements. If two integers are equal, it can also be regarded as a special case of increasing sequence.


class Solution {<!-- -->
public:
    vector<vector<int>> res;
    vector<int> path;
    void track(vector<int> & amp; nums,int start){<!-- -->
        if(path.size()>1){<!-- -->
            res.push_back(path);
        }
        unordered_set<int> uset;
        for(int i=start;i<nums.size();i + + ){<!-- -->
            if((!path.empty() & amp; & amp;nums[i]<path.back())||uset.find(nums[i])!=uset.end()){<!-- -->
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            track(nums,i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int> & amp; nums) {<!-- -->
        res.clear();
        path.clear();
        track(nums,0);
        return res;
    }
};






 void track2(vector<int> & amp;nums,int start){<!-- -->
        if(path.size()>1){<!-- -->
            res.push_back(path);
        }
        int used[201]={<!-- -->0};//The range of integers in the array is [-100,100].
        for(int i=start;i<nums.size();i + + ){<!-- -->
            if((!path.empty() & amp; & amp;nums[i]<path.back())||(used[nums[i] + 100]==1)){<!-- -- >
                continue;
            }
            used[nums[i] + 100]=1;
            path.push_back(nums[i]);
            track2(nums,i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int> & amp; nums) {<!-- -->
        res.clear();
        path.clear();
        track2(nums,0);
        return res;
    }



Title: Full Arrangement


Given an array nums without repeated numbers, return all possible permutations of it. You can return answers in any order.


First of all, the arrangement is ordered, that is to say, [1,2] and [2,1] are two sets, which is different from the previously analyzed subsets and combinations. It can be seen that element 1 has been used in [1,2], but 1 is used again in [2,1], so there is no need to use start to deal with the arrangement problem. But the arrangement problem requires a used array to mark the selected elements, as shown in the orange part of the figure:






Because of the arrangement problem, the search must be started from the beginning every time. For example, element 1 has been used in [1,2], but 1 has to be used again in [2,1]. The used array actually records which elements in the path are used at this time. An element can only be used once in an arrangement.


class Solution {<!-- -->
public:
    vector<vector<int>> res;
    vector<int> path;
    void track(vector<int> & amp;nums,vector<bool> & amp;used){<!-- -->
        if(path.size()==nums.size()){<!-- -->
            res.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i + + ){<!-- -->
            if(used[i]==true) continue;
            used[i]=true;
            path.push_back(nums[i]);
            track(nums,used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int> & amp; nums) {<!-- -->
        res.clear();
        path.clear();
        vector<bool> used(nums.size(),false);
        track(nums,used);
        return res;
    }
};



Time complexity: O(n!); Space complexity: O(n). The difference in the arrangement problem: each layer starts searching from 0 instead of start, and the used array is needed to record which elements are placed in the path.


Title: Full Arrangement II


Given a sequence nums that may contain repeated numbers, in any order returns all non-repeating permutations.


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



It should also be emphasized that elements must be sorted to remove duplicates, so that we can easily judge whether they are reused through adjacent nodes.





In the figure, we use the same tree layer. If the previous bit (that is, nums[i-1]) has been used, then we will remove the duplicates. Generally speaking: combination problems and permutation problems collect results on the leaf nodes of the tree structure, while subset problems collect the results of all nodes on the tree. Time complexity: O(n! * n)