C++, Backtracking, concise code


  • 0
    Z
    class Solution {
    public:
        bool canPartitionKSubsets(vector<int>& nums, int k) {
            int sum = 0;
            for (int i:nums) sum += i;
            if (sum%k != 0) return false;
            // optimization, try large number first
            sort(nums.begin(), nums.end(), greater<int>());
            return helper(nums, 0, k, 0, sum/k);
        }
    private:
        // visited, use bit manipulation to record whether nums[i] has been used
        bool helper(vector<int>& nums, int visited, int k, int sum, int tar){
            if (k == 1) return true;
            for (int i = 0; i < nums.size(); i++) {
                if (((visited>>i)&1) == 0) {
                    if (sum+nums[i] < tar && helper(nums, visited|(1<<i), k, sum+nums[i], tar)) return true;
                    if (sum+nums[i] == tar && helper(nums, visited|(1<<i), k-1, 0, tar)) return true;
                    // optimization, if sum = 0, it must use first available number
                    if (sum == 0) break;
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.