[Java/C++]Straightforward dfs solution


  • 21

    Update: This question has been changed after the contest. It added the special restriction 0 < nums[i] < 10000. My solution here is without that consideration.

    Assume sum is the sum of nums[] . The dfs process is to find a subset of nums[] which sum equals to sum/k. We use an array visited[] to record which element in nums[] is used. Each time when we get a cur_sum = sum/k, we will start from position 0 in nums[] to look up the elements that are not used yet and find another cur_sum = sum/k.

    An corner case is when sum = 0, my method is to use cur_num to record the number of elements in the current subset. Only if cur_sum = sum/k && cur_num >0, we can start another look up process.

    Some test cases may need to be added in:
    nums = {-1,1,0,0}, k = 4
    nums = {-1,1}, k = 1
    nums = {-1,1}, k = 2
    nums = {-1,1,0}, k = 2
    ...

    Java version:

        public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum = 0;
            for(int num:nums)sum += num;
            if(k <= 0 || sum%k != 0)return false;
            int[] visited = new int[nums.length];
            return canPartition(nums, visited, 0, k, 0, 0, sum/k);
        }
        
        public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target){
            if(k==1)return true;
            if(cur_sum == target && cur_num>0)return canPartition(nums, visited, 0, k-1, 0, 0, target);
            for(int i = start_index; i<nums.length; i++){
                if(visited[i] == 0){
                    visited[i] = 1;
                    if(canPartition(nums, visited, i+1, k, cur_sum + nums[i], cur_num++, target))return true;
                    visited[i] = 0;
                }
            }
            return false;
        }
    

    C++ version:

        bool canPartitionKSubsets(vector<int>& nums, int k) {
            int sum = 0;
            for(int num:nums)sum+=num;
            if(k <= 0 || sum%k != 0)return false;
            vector<int> visited(nums.size(), 0);
            return canPartition(nums, visited, 0, k, 0, 0, sum/k);
        }
        
        bool canPartition(vector<int>& nums, vector<int>& visited, int start_index, int k, int cur_sum, int cur_num, int target){
            if(k==1)return true;
            if(cur_sum == target && cur_num >0 )return canPartition(nums, visited, 0, k-1, 0, 0, target);
            for(int i = start_index; i<nums.size(); i++){
                if(!visited[i]){
                    visited[i] = 1;
                    if(canPartition(nums, visited, i+1, k, cur_sum + nums[i], cur_num++, target))return true;
                    visited[i] = 0;
                }
            }
            return false;
        }
    

  • 2

    @Vincent-Cai The description restricts 0 < nums[i] < 10000. Therefore, sum is always greater than 0.


  • 0

    @Vincent-Cai Nice logic! I failed to figure out that this was a backtracking question. But now that I think about it in retrospect, I think it should have been evident. No worries, next time! :)

    I thought it to be pretty similar to two-sum. But I am not sure if that approach can be used here. Once I understand the target, I will simply look up to find pairs of numbers (or individual numbers) that sum to target. But I am not totally sure if that works. I will try and update this post. In the meanwhile, anyone, any comments?


  • 0

    @Aoi---silent Thanks for your explanation. I think they changed the question description today, there was no such restriction description in the contest.


  • 0
    Y

    Great idea! Add my modified version below. I think it will be faster if we sort the array first.

        public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % k != 0) {
                return false;
            }
            boolean[] visited = new boolean[nums.length];
            Arrays.sort(nums);
            return canPartition(nums, visited, k, 0, 0, sum / k);
        }
        
        private boolean canPartition(int[] nums, boolean[] visited, int k, int start, int curSum, int target) {
            if (k == 1) {
                return true;
            }
            if (curSum == target) {
                return canPartition(nums, visited, k - 1, 0, 0, target);
            }
            for (int i = start; i < nums.length; i++) {
                if (visited[i]) {
                    continue;
                }
                if (curSum + nums[i] > target) {
                    break;
                }
                visited[i] = true;
                if (canPartition(nums, visited, k, i + 1, curSum + nums[i], target)) {
                    return true;
                }
                visited[i] = false;
            }
            return false;
        }
    

  • 0
    B

    In function canPartition add a line code if (cur_sum > target)return false. It will be super fast.

    In Java

    public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target){
            if (cur_sum > target)return false; // add this one
            if(k==1)return true;
            if(cur_sum == target && cur_num>0)return canPartition(nums, visited, 0, k-1, 0, 0, target);
            for(int i = start_index; i<nums.length; i++){
                if(visited[i] == 0){
                    visited[i] = 1;
                    if(canPartition(nums, visited, i+1, k, cur_sum + nums[i], cur_num++, target))return true;
                    visited[i] = 0;
                }
    

  • 0

    @biss Thanks! You can see the update of this post.


  • 0
    L

    @Yuchong somehow it's slower, but I dont understand why


  • 0

    @levin1412 I have tried it as well and found the reason. It is becasue he sorted it in the wrong order. For this solution, bigger number should come first.


  • 0
    S

    @BatCoder My first thought was also similar to the 2-sum problem. However, after a second thought, I am afraid the similar approach cannot work here.

    In 2-sum, we can ensure that if we find a sub-array whose sum is target (half of the total sum), the remaining elements also give a sum equal to target.

    Here, for the k-partition, if k > 1, the same logic doesn't apply. Take the problem statement as an example:

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

    If our algorithm, unfortunately, first locates (1, 2, 2) as a candidate sub-array whose sum is 5, then obviously we cannot find the other 3 sub-arrays.

    However, with backtracking, it seems we will test every possible combination until we find one. Thus, the above problem doesn't exist.

    What's your thought now?


  • 0

    @shuhua, you say "If our algorithm, unfortunately, first locates (1, 2, 2) as a candidate sub-array whose sum is 5, then obviously we cannot find the other 3 sub-arrays." However, I am not sure how this could be true. Because as per the problem statement of 2-sum, we find just two numbers that sum to a given value. So, in my opinion, (1, 2, 2) as a solution is not possible.

    The reason I am skeptical about 2-sum is because of its constraints:

    • Each input would have exactly one solution
    • You may not use the same element twice

    which, I think, might not necessarily be true for this question. Besides, the complexity would be O(n^2).

    What do you think?


  • 1
    T

    whats the complexity


  • 1
    Y

    adding a restriction to cut off invalid branches, the performance will be better in terms time complexity.
    if (cur_sum > target) {
    return false;
    }


  • 0

    @Yang0616 Please see the "update" in the post :).


  • 0
    K

    Any pointers regarding the time complexity calculation for the provided solution


  • 0

    @terminator123456 I think it's O(2^N).


  • 0

    Is this an NP-complete problem? I think it is a reduction of "Subset sum problem".
    Neat code.


  • 0
    6

    I start the loop from zero every time and check whether the element has been used, but I get TLE. Is the start_index makes such a big difference to the performance?
    my loop is like this:

             for(int i = 0; i < nums.length; i++) {
                if(!used[i] && sum + nums[i] <= target) {
                    used[i] = true;
                    if(helper(nums, used, k, count+1, sum+nums[i], target)) {
                        return true;
                    }
                    used[i] = false;
                }
             }
    

  • 1
    T

    This is a Backtracking, not DFS algorithm. DFS has linear complexity and this one has exponential one.


  • 0
    C

    @tarasevich Can you elaborate on "DFS has linear complexity"? In terms of what?
    Don't you have to backtrack when performing DFS? The solution presented in this thread is searching branches in the tree where each branch is a possible way of allocating a number to one of the k sets, in a depth-first manner, isn't it?


Log in to reply
 

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