回溯算法

回溯算法(backtrack algorithm)实际上就是深度优先搜索(DFS), 它首先将下一个节点添加进去，然后进行下一步运算，如果到后面发现不满足条件就转回来，将之前添加的节点去除重新添加其他的节点，然后进行运算，直到最后满足条件或是将所有可能都枚举完成。由于回溯算法需要枚举出多种可能很有可能会导致超时，所以在使用回溯算法的时候通常会进行一些优化，也就是剪枝操作。

473. Matchsticks to Square

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Example 1:
Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.
Constraints:

1 <= matchsticks.length <= 15

1 <= matchsticks[i] <= 108

回溯算法的大概思路为：首先将第1根火柴放在第一条边中，如果边长小于之前计算的边长则迭代调用dfs函数将第2根火柴放在第1条边中，如果此时不满足条件了就会使用edges[i] -= matchsticks[index];将这根火柴取出，如果将第2根火柴放在第二条边中，如果第二根火柴可以放在第二条变中则迭代第三根火柴，这是还是先检测这第三根火柴是否可以放在第一条边中。这样回溯可以将所有可能的情况都枚举出来，自然可以获取最后的答案。因为枚举的算法复杂度太高，所以需要进行优化，一般可以从下面几个方面入手

先进行排序，将大的放在前面

因为如果把较大的元素放在前面可以减小回溯的周期

迭代完成之后可以直接返回true

因为我们设置的条件是，每条边的长度是总长度的四分之一，所以当全部火柴都用完了，一定是拼成了一个正方形

当i > 0 时，如果第i条边的长度同i-1的长度相同可以直接使用continue语句

因为既然把这根火柴加在第i-1条边上产生了回溯，并且i条边的长度与i-1条边的长度相同，所以加在i条边长一定会产生回溯，所以可以直接跳过。

class Solution {
    // index表示第index根火柴，
    bool dfs(int index, vector<int> &matchsticks, vector<int> &edges, int len) {
        if (index == matchsticks.size()){       // 火柴枚举完了，可以直接返回true
            return true;
        }
        for (int i = 0; i < edges.size(); i++) {        // 回溯算法的核心部分
            if(i > 0 && edges[i] == edges[i-1]){continue;}      // 优化算法，减少不必要的枚举
            edges[i] += matchsticks[index];
            if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)) {
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;
    }
public:
    bool makesquare(vector<int> &matchsticks) {
        // 计算总长度
        int totalLen = accumulate(matchsticks.begin(), matchsticks.end(), 0);       
        if (totalLen % 4) {        // 如果不是4的整数直接返回false
            return false;
        }
        // 从大到小排序，减少搜索量
        sort(matchsticks.begin(), matchsticks.end(), greater<int>()); 
        // 表示四条边的边长
        vector<int> edges(4);
        return dfs(0, matchsticks, edges, totalLen / 4);
    }
};

5289. Fair Distribution of Cookies

You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith bag. You are also given an integer k that denotes the number of children to distribute all the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.

The unfairness of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.

Return the minimum unfairness of all distributions.

Example 1:
Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Explanation: One optimal distribution is [8,15,8] and [10,20]
- The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies.
The unfairness of the distribution is max(31,30) = 31.
It can be shown that there is no distribution with an unfairness less than 31.
Example 2:
Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies.
The unfairness of the distribution is max(7,7,7) = 7.
It can be shown that there is no distribution with an unfairness less than 7.
Constraints:

2 <= cookies.length <= 8

1 <= cookies[i] <= 105

2 <= k <= cookies.length

这个和上面的那道题差不多，不过这个回溯的时候不需要条件，只需要在结束处比较获得答案

class Solution {
    int n;      // number of cookies bags
    int kk;     // number of childer
    int ans = 1e6;      // final answer, initial big value
    void dfs(int index, vector<int>& cookies, vector<int>& bucket){
        if(index == n){     // when the cookies distributie over
            ans = min(ans, *max_element(bucket.begin(), bucket.end()));     // renew answer
            return;
        }
        // optimize: if one child get more cookie than answer
        for(int i = 0; i < kk; i++){
            if(bucket[i] > ans){return;}
        }

        for(int i = 0; i < kk; i++){    // core code
            bucket[i] += cookies[index];
            dfs(index+1, cookies, bucket);
            bucket[i] -= cookies[index];
        }
        return;
    }
public:
    int distributeCookies(vector<int>& cookies, int k) {
        n = cookies.size();
        kk = k;
        vector<int>bucket(k, 0);
        // optimize, push greater number in front
        sort(cookies.begin(), cookies.end(), greater<int>());   
        dfs(0, cookies, bucket);
        return ans;
    }
};

46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints:

1 <= nums.length <= 6

-10 <= nums[i] <= 10

All the integers of nums are unique.

这题的回溯与上面不同点在于上面的回溯都是相当于有几个桶，然后向桶里面添加元素，这个则是交换元素。回溯需要注意的关键点在于first参数是什么意思，这里first表示交换点在上面地方

class Solution {
    int len;
    vector<vector<int> > res;
public:
    void backtrack(vector<int>& output, int first){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        len = nums.size();
        backtrack(res, nums, 0);
        return res;
    }
};