22.括号生成

 22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 

思路：回溯算法最佳实践：括号生成 :: labuladong的算法小抄 (gitee.io)

合法括号组合满足的性质：

1.右括号数等于右括号数 ;

2.对于一个合法的括号组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。（因为是从左往右读的）

回溯思路：

1.回溯算法的过程中要穷举所有组合（满足题目条件的组合/不满足题目条件的组合）；

2.从所有组合中排除不满足条件的组合，最后得到满足条件的组合。

具体而言：

1.在此位置先放左括号，进行backTrack递归，就相当于以左括号为根节点生成一棵子多叉树，当走到 if ( left == 0 && right == 0 ) 时就可以记录下“正确的组合”，否则在 if ( left > right )和if ( left < 0 || right < 0 ) 就返回了。

2.撤销左括号，意思就是这棵子多叉树已经走完了，下面准备再试试在此位置放置右括号会有哪些“正确的组合”。

3.右括号同理。

class Solution {
public:
    vector res;
    vector generateParenthesis(int n) {
        string track;
        backtrack(n,n,track);//左右括号各有n个
        return res;
    }
    void backtrack(int left,int right,string& track)
    {
        if(left>right)//左括号剩下的比右括号多，不合法的括号组合
        {
            return ;//剪枝
        }
        if(left<0||right<0)
        {
            return ;//剪枝
        }
        if(left==0&&right==0)//当两边括号都恰好用完时，得到一个合法的括号组合
        {
            res.push_back(track);
            return ;//子决策树到此为止，也是在剪枝
        }
        //尝试放一个左括号
        track.push_back('(');//做选择
        backtrack(left-1,right,track);
        track.pop_back();//撤销选择
 
        //尝试放一个右括号
        track.push_back(')');//做选择
        backtrack(left,right-1,track);
        track.pop_back();//撤销选择
    }
};

698. 划分为k个相等的子集

labuladong 题解思路

给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

示例 2:

输入: nums = [1,2,3,4], k = 3
输出: false

思路：回溯算法 

将n个数划分为k个等和子集，转换下就是，把n个数放进k个集合里，要让k个集合里的数字之和相同。回溯算法要求我们首先找到选择列表，那么从k个集合的视角来看，选择列表就是那n个数，做选择就是选里面的一个数加入桶中，当一个桶中的数字之和达到目标时，就换下一个桶继续，直到所有的桶都装够目标。使用bucket数组来记录每个桶的状态，使用used数组来记录每个数字的使用情况，被用过了就不能再用了。

和解数独这道题类似，这个题的backtrack函数的返回值也要设置为bool类型，因为一旦找到所有桶都装够了目标的情况就要赶紧返回，结束回溯（不然一直回溯下去又会回到原状态）。所以设置bool类型返回值，在每次backtrack时都检验一下返回值是否为true，是true，就结束回溯。

37.解数独(内含回溯算法重要思路)_{(sunburst)}的博客-CSDN博客

但是这样做完，时间复杂度还是很高，需要使用备忘录来记录桶的状态和对应的结果，如果在回溯的过程中遇到同样的桶的状态，就直接返回结果，不需要再执行下面的操作，使得时间大大缩短。

class Solution {
public:
    unordered_mapbool> memo;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum%k!=0) 
            return false; 
        int target=sum/k;
        int n=nums.size();
        vector<int> bucket(k,0);
        vector<bool> used(n,false);
        return backtrack(k,0,nums,0,used,target);
    }
    bool backtrack(int k, int cur,vector<int>& nums,int start,vector<bool>& used,int target)
    {
        if(k==0)
            return true;
        string state;
        for(bool u:used)
        {
            if(u) state+='1';
            else  state+='0';
        }
        if(memo.count(state))
        {
            return memo[state];
        }
        if(cur==target)
        {
            bool res=backtrack(k-1,0,nums,0,used,target);
            memo[state]=res;
            return res;
        }
        for(int i=start;isize();i++)
        {
            if(used[i])
            {
                continue;
            }
            if(cur+nums[i]>target)
            {
                continue;
            }
            cur+=nums[i];
            used[i]=true;
            if(backtrack(k,cur,nums,i+1,used,target))
                return true;
            cur-=nums[i];
            used[i]=false;
        }
        return false;
    }
};