<commit_before>//  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};<commit_msg>:art: Clean partition code<commit_after>//  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) {
    if (placing == ((1 << nums.length) - 1)) return true;

    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))));
          return true;
          // 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 false; //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;
    // to see if the valid placing will via this placling : (1 << nums.length) - 1
    //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};
{'fraction_non_alphanumeric': 0.17790719519068193, 'fraction_numerical': 0.0187863986473793, 'mean_word_length': 2.7282913165266107, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 11, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3144630', 'n_tokens_mistral': 1748, 'n_tokens_neox': 1657, 'n_words': 523}