698. Partition to K Equal Sum Subsets

發表於 | 分類於

problem17. Letter Combinations of a Phone Number

solution

option 1 - dfs , maybe TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool backtracking(vector<int>& nums, vector<bool> & visited, int start, int sum, int target, int k){
        if(k==0) return true;
        if(target == sum){
            return backtracking(nums, visited, 0,0,target , k-1);
        }
        
        for(int i=start;i<nums.size() ; ++i){
            if(visited[i] || sum+nums[i] > target) continue;
            sum+=nums[i];
            visited[i] = true;
            if(backtracking(nums, visited, i+1,sum, target, k) ) return true;
            sum-=nums[i];
            visited[i] = false;
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        int total = 0;
        for(int n:nums) total +=n;
        if(total%k!=0) return false;
        vector<bool> visited(n, false);
        total/= k;
        return backtracking(nums, visited, 0, 0, total, k);
    
    }
};