# 0698. Partition to K Equal Sum Subsets
###### tags: `Leetcode` `Medium` `Backtracking` `FaceBook`
Link: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
## 思路
[0416. Partition Equal Subset Sum](https://hackmd.io/18plVWdQSjutpHD_ownwSg)的进阶版
用visited记录每条路上之前用了哪些数
用Line 17里的```currSum+nums[i]<=target```剪枝 加了之后速度显著提升
时间复杂度计算：不考虑剪枝的情况 相当于对于nums里面的每个数字都考虑一遍它是否会出现在每个subset里面（一共k个）
**backtracking的时间复杂度一般都是排列组合，且不考虑剪枝**
## Code

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        if(k==1) return true;
        if(k > nums.length) return false;
        if(sum%k != 0) return false;
        boolean[] visited = new boolean[nums.length];
        return backtracking(nums, k, sum/k, 0, 0, visited);
    }
    public boolean backtracking(int[] nums, int k, int target, int currSum, int startIdx, boolean[] visited){
        if(k==0) return true;
        if(currSum == target) return backtracking(nums, k-1, target, 0, 0, visited);
        for(int i = startIdx;i < nums.length;i++){
            if(!visited[i] && currSum+nums[i]<=target){
                visited[i] = true;
                if(backtracking(nums, k, target, currSum+nums[i], i+1, visited)) return true;
                visited[i] = false;
            }
        }
        return false;
    }
}