Backtracking 两道题 (Leetcode 464,

把两道比较难的Backtracking的类似题放到一起，总结一下格式。

两道题的具体讲解参考youtube：
https://www.youtube.com/watch?v=md3qQ-5B0aU&t=1199s

两道题都是要建立状态数组，并在recursion时遍历状态数组。注意backtracking时把状态设回来。

Can I Win (464)

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int maxSum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
        if(maxSum < desiredTotal) return false;
        vector<int> subset(maxChoosableInteger+1, 0);
        return canwin(subset, desiredTotal);
    }
    
    bool canwin(vector<int> &subset, int total){
        string cur = convertString(subset);
        if(mp.count(cur)) return mp[cur];
        
        for(int i=1; i<subset.size(); i++){
            if(subset[i] == 0){
                subset[i] = 1;
                if(total - i <= 0 || !canwin(subset, total-i)){
                    mp[cur] = true;
                    subset[i] = 0;
                    return true;
                }
                subset[i] = 0;
            }
        }
        mp[cur] = false;
        return false;
    }
    
    string convertString(vector<int> &subset){
        string s = "";
        for(int it : subset){
            s += '0' + it;
        }
        return s;
    }
private:
    unordered_map<string, bool> mp;
};

Partition to K Equal Sum Subsets (698)

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        if(nums.empty()) return false;
        int sum = accumulate(begin(nums), end(nums), 0, plus<int>());
        if(sum % k != 0) return false;
        
        int target = sum / k;
        // cout << target << endl;
        sort(nums.begin(), nums.end());
        
        int beginIndex = nums.size()-1;
        if(nums[beginIndex] > target) return false;
        
        while(beginIndex >= 0 && nums[beginIndex] == target){
            beginIndex--;
            k--;
        }
        
        vector<int> subSet(k, 0);
        return partition(subSet, nums, beginIndex, target);
    }
    
    bool partition(vector<int> &subset, vector<int>& nums, int index, int target){
        if(index < 0){
            return true;
        }
        int selected = nums[index];
        for(int i=0; i<subset.size(); i++){
            if(subset[i] + selected <= target){
                subset[i] += selected;
                if(partition(subset, nums, index-1, target)){
                    return true;
                }
                subset[i] -= selected;
            }
        }
        return false;
    }
};