###### tags: `LeetCode` `Medium` `DFS`
# LeetCode #698 [Partition to K Equal Sum Subsets](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/)
### (Medium)

給定一個整數數組 nums 和一個正整數 k，找出是否有可能把這個數組分成 k 個非空子集，其總和都相等。

---
首先可以先將nums排序, 並計算總和以及每個組合的元素和, 若元素和不為整數則回傳空集合。

接下來使用DFS找組合, 每找到一組則從頭開始尋找新的組合, 並將組合數+1, 若組合數等同於k, 則回傳true, 若找完全部組合皆沒達成組合數等於k, 則回傳false。

幾個要點:
1. 當找到新的組合時(sum==total/k), 要回傳的是從頭開始, 但組合數+1的DFS
2. 由於找到新的組合後須從頭開始找, 因此不能用`if(i!=pos&&nums[i]==nums[i-1])continue;`來跳過重複值, 這會跳過所有不是第一個的重複值, 而非其原本的用意: 在DFS探索失敗"返回"後, 跳過探索必定失敗的重複值。

差別在於這題是探索成功後尋找其他組合, 而非探索失敗後"返回"再尋找其他組合。因此本題需要使用last來辨識用過的值。

---

class Solution {
public:
    int total;
    int visited[16];
    int k;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        this->k = k;
        total = accumulate(nums.begin(), nums.end(), 0);
        sort(nums.begin(), nums.end());
        if(total%k!=0)return false;
        return dfs(0,0,0, nums);//pos, group, sum
    }
    bool dfs(int pos, int group, int sum, vector<int>& nums){
        if(sum>total/k)return false;
        if(sum==total/k)return dfs(0, group+1, 0, nums);
        if(group==k)return true;
        int last=-1;
        for(int i=pos;i<nums.size();i++){
            
            if(visited[i])continue;
            //if(i!=pos&&nums[i]==nums[i-1])continue;//不能這樣寫
            if(nums[i]==last)continue;
            visited[i]=1;
            last=nums[i];
            if(dfs(i+1, group, sum+nums[i], nums))return true;
            visited[i]=0;
        }
        return false;
    }
};