1.回溯

1.组合与组合总和

共性：解集不重复（无序）

组合问题：寻找一个数组中的组合数

组合总和：寻找一个无重复数组中的总和为target的组合（同一元素可以重复在一个组合中使用）

回溯时starindex不变！

组合总和Ⅱ：寻找一个有重复数组中总和为target的组合（同一元素不可以重复使用）

“使用过”两层含义：同层不重复，同枝可重复

引入used数组，要排序

组合总和Ⅲ：寻找一个无重复数组（1-9）中总和为target的组合（同一元素不可以重复使用）

回溯时starindex + 1 ！

2.子集

子集：数组不重复，找出所有子集

常规回溯

子集Ⅱ：数组重复，找出所有不重复子集

需要去重，用used数组+排序

递增子序列：数组重复，找出不重复递增子序列

因为要找递增子序列，不许排序，所以用set去重

3.排列

全排列：

不需要starindex，但需要used来判断是否使用过

全排列Ⅱ：数组有重复，找无重复排列

也需要used，但是used有排列的筛选功能和前面的去重（used+排序）的功能

4.数组

螺旋矩阵：

//错解：
//bug1:越界bug
//bug2:要坚持左闭右开原则
//bug3:非方阵怎么办
//为解决bug：没有办法处理非方阵
vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //bug1:越界bug
        //bug2:要坚持左闭右开原则
        //bug3:非方阵怎么办
        vector<int> res;
        int startx = 0;
        int starty = 0;
        int offset = 1;
        int n = matrix.size();
        int m = matrix[0].size();
        int loop = min(m,n) / 2;
        int i = 0;
        int j = 0;
        while(loop--){
            ////在每次循环（每一层）完成后，应重置 startx 和 starty 到新起点，
            //而不是直接递增它们。并且，需要避免对最后一个元素重复添加或越界访问。
            i = startx;
            j = starty;
            
            for(;i < m - offset; i++){
                res.push_back(matrix[j][i]);
            }
            for(;j < n - offset; j++){
                res.push_back(matrix[j][i]);
            }
            for(;i > startx; i--){
                res.push_back(matrix[j][i]);
            }
            for(;j > starty; j--){
                res.push_back(matrix[j][i]);
            }
            startx++;
            starty++;
            offset++;   
        }
        if(min(m, n) % 2 != 0){
             res.push_back(matrix[n/2][m/2]);
        }
        return res;
    }

//正解
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return {};
        int l = 0, r = matrix[0].size() - 1, t = 0, b = matrix.size() - 1;
        vector<int> res;
        while (true) {
            for (int i = l; i <= r; i++) res.push_back(matrix[t][i]); // left to right
            if (++t > b) break;
            for (int i = t; i <= b; i++) res.push_back(matrix[i][r]); // top to bottom
            if (l > --r) break;
            for (int i = r; i >= l; i--) res.push_back(matrix[b][i]); // right to left
            if (t > --b) break;
            for (int i = b; i >= t; i--) res.push_back(matrix[i][l]); // bottom to top
            if (++l > r) break;
        }
        return res;
    }
};
​
​