//  Copyright 2017 The KeepTry Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

package numberPartitioning;

import java.util.Arrays;

// DP

/**
 * @see <a href="https://leetcode.com/articles/partition-to-k-equal-sum-subsets/">Leetcode</a>
 */
public class Leetcode698PartitiontoKEqualSumSubsets2 {
  static boolean recursion(int placing, int leftSum, boolean[] isValid, int[] nums, int ave) {
    for (int i = 0; i < nums.length; i++) {
      if ((((1 << i) | placing) != placing) && nums[i] <= ((leftSum - 1) % ave + 1)) {
        // System.out.println(String.format("try %6s", Integer.toBinaryString(placing | (1 << i))));
        if (recursion(placing | (1 << i), leftSum - nums[i], isValid, nums, ave)) {
          // System.out.println(String.format("works %6s", Integer.toBinaryString(placing | (1 << i))));
          isValid[placing] = true;
          break;
        }
        // else
        //   System.out.println(String.format("not works %6s", Integer.toBinaryString(placing | (1 << i))));
      }
    }

    // if (isValid[placing] == true)
    //  System.out.println(String.format("valid order %6s", Integer.toBinaryString(placing)));
    return isValid[placing];
  }

  public static boolean canPartitionKSubsets(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k < 1 || k > nums.length) return false;
    int sum = Arrays.stream(nums).sum();
    if (sum % k > 0) return false;

    boolean[] isValid = new boolean[1 << nums.length];
    isValid[(1 << nums.length) - 1] = true;
    //System.out.println(String.format("default %6s is true", Integer.toBinaryString((1 << nums.length) - 1)));
    return recursion(0, sum, isValid, nums, sum / k);
  }

  //---------------------------------------------------
  public static void main(String[] args) {

    int[] nums = new int[] {1, 2, 3, 4, 5, 6};
    int k = 3;
    System.out.println(" -- okay -- ");
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums = new int[] {4, 2, 2, 3, 6, 6, 1};
    k = 4;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums = new int[] {2, 1, 2, 2, 1, 1};
    k = 3;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums = new int[] {2, 2, 2, 2, 2, 2};
    k = 3;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums = new int[] {3, 1, 1, 2, 1, 1};
    k = 3;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums = new int[] {2, 2, 2, 1, 1, 1};
    k = 3;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");

    System.out.println(" -- false -- ");
    nums = new int[] {3, 1, 1, 2, 1, 1};
    k = 7;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums = new int[] {3, 1, 1, 2, 1, 1};
    k = 0;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums = null;
    k = 2;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums = new int[] {3, 1, 1, 2, 1, 1};
    k = 2;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
    nums =
        new int[] {
          5, 5, 5, 5, 5,
          5, 5, 5, 5, 5,
          5, 5, 5, 5, 5,
          5
        };
    k = 5;
    System.out.println(canPartitionKSubsets(nums, k) == true ? "Can  " : "No ");
  }
}

@@ -671,19 +671,16 @@
  DP%0A%0A/**
-%0A *
  @see %3Ca
@@ -763,17 +763,16 @@
 code%3C/a%3E
-%0A
  */%0Apubl
@@ -913,24 +913,83 @@
  int ave) %7B%0A
+    if (placing == ((1 %3C%3C nums.length) - 1)) return true;%0A%0A
     for (int
@@ -1406,16 +1406,42 @@
         
+ return true;%0A          //
  isValid
@@ -1466,16 +1466,20 @@
         
+  //
   break;
@@ -1628,17 +1628,16 @@
 %7D%0A    %7D%0A
-%0A
     // i
@@ -1771,16 +1771,25 @@
  return 
+false; //
 isValid%5B
@@ -2085,16 +2085,16 @@
 ength%5D;%0A
-
     isVa
@@ -2125,24 +2125,107 @@
  1%5D = true;%0A
+    // to see if the valid placing will via this placling : (1 %3C%3C nums.length) - 1%0A
     //System

Clean partition code