###### tags: `Leetcode` `medium` `dfs` `backtracking` `array` `python` `c++`

# 698. Partition to K Equal Sum Subsets

## [題目連結:] https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

## 題目:
Given an integer array ```nums``` and an integer ```k```, return ```true``` if it is possible to divide this array into ```k``` non-empty subsets whose sums are all equal.

**Example 1:**

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

**Example 2:**

Input: nums = [1,2,3,4], k = 3
Output: false

## 解題想法:
* 此題為給一數組，判斷是否能將其元素分配成k個集合使其每個集合總和相等
* backtracking:
* 想法: 先將元素**由大到小排好**，依序放置於k個集合
* Step1: 初始
* sub=[0] * k (創建k個集合)
* nums.sort(reverse=True) (需由大到小排好)
* return dfs()
* Step2: dfs函式(nums, k, target, cur_pos, sub)
* **想法**: 將當前數字nums[cur_pos]，從第一個sub放 ，若滿了，則改放於第二個sub......以此類推
* **終止條件**:
* if cur_pos==len(nums): return True
* 能順利全部數字都放完
* **迴圈判斷**:
* 看目前此數字nums[cur_pos]可以填入哪個sub
* for i in range(k):
* 先將此數字加入: sub[i]+=nums[cur_pos]
* **Case1**: 若仍再安全範圍且下個數也可以放入任意sub中(遞迴)，return True
* **Case2**: 當前sub已裝滿，需將此數字踢掉，換給下個sub試
* 注意，若踢掉該num[cur_pos]後，此sub容量大小為初始0，**表示即使num[cur_pos]放入該sub，後續數值也放不進任一sub中**，所以直接break回傳False讓上層遞迴知道目前有問題

## Python:

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        sub=[0]*k
        target=sum(nums)//k
        if sum(nums)%k!=0:
            return False
        nums.sort(reverse=True) #由大到小排好
        return self.dfs(nums,k,target,0,sub)
    #從sub第一個放 若滿了 放到sub第二格 以此類推
    def dfs(self,nums,k,target,cur_pos,sub):
        if cur_pos==len(nums):
            return True
        for i in range(k): #看目前此數字nums[cur_pos]可以填入哪個sub
            sub[i]+=nums[cur_pos]
            #若仍再安全範圍且下個數也可以放入任意sub中
            if sub[i]<=target and self.dfs(nums,k,target,cur_pos+1,sub):
                return True
            else: #滿了 將新加入的踢掉
                sub[i]-=nums[cur_pos]
                if sub[i]==0: 
                    break 
                '''
                若踢掉該num[cur_pos] 此sub容量大小為初始0
                表示即使num[cur_pos]放入該sub 後續數值也放不進任一sub中
                所以直接break回傳False讓上層遞迴知道目前有問題
                '''
        return False

nums =[3,9,4,5,8,8,7,9,3,6,2,10,10,4,10,2]
k = 10
result=Solution()
ans=result.canPartitionKSubsets(nums,k)
print(ans)

## C++:
* Sort the vector in descending order
* sort(a.begin(), a.end(), greater<int>());

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    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;
        vector<int> sub(k, 0);
        // Sort the vector in descending order
        sort(nums.begin(), nums.end(), greater<int>());
        return dfs(nums, k, target, 0, sub);
    }

    bool dfs(vector<int>& nums, int k, int target, int curPos, vector<int>& sub){
        if (curPos==nums.size())
            return true;
        for (int i=0; i<k; i++){
            sub[i]+=nums[curPos];
            if (sub[i]<=target && dfs(nums, k, target, curPos+1, sub))
                return true;
            else{
                sub[i]-=nums[curPos];
                if (sub[i]==0)
                    break;
            }
        }
        return false;
    }
};