# LinkedIn Interview

canPartitionKSubsetsHelper
unknown
plain_text
2 years ago
2.3 kB
5
Indexable
Never
```// public class HelloWorld {

//   public static void main(String[] args){
//     //Prints "Hello, World" to the terminal
//     System.out.println("Hello, World");
//   }

// }

// /**
//  * This function determines if the braces ('(' and ')') in a string are properly matched.
//  * it ignores non-brace characters.
//  * Some examples:
//  * "()()()()"   -> true
//  * "((45+)*a3)" -> true
//  * "(((())())"  -> false
//  * "))((" -> false
//  */
//  public boolean matched(String s) {

//    Stack<Character> stack = new Stack<>();

//    for (Character c : s) {
//      switch(c)
//        case '(':
//         stack.push(')');
//        case ')':
//         if (stack.isEmpty()) {
//           return false;
//         }
//         stack.pop();
//        default:
//         continue;
//    }

//    return stack.isEmpty();
//  }

// Given an integer array of random number, and given parameter k, determine whether it is possible to divide the array into k subsets whose sums are equivalent to each other.

// Example: given [4, 3, 2, 3, 5, 2, 1] and k=4. It's possible to divide it into 4 sub arrays (5), (1, 4), (2,3), (2,3).
sum = 5;

// Example 2: given [3, 1, 1, 2, 4, 4] and k=3, It's possible to divide it into 3 sub arrays (3,2), (1,4), (1,4).

public boolean canPartitionKSubsets(int[] nums, int k) {

int sum = 0;
int total = 0;
for (int i : nums) {
total += nums[i];
}
if (total % sum > 0) {
return false;
}

return canPartitionKSubsetsHelper(nums, k, sum, sum, 0, New boolean[nums.length]);

}

public boolean canPartitionKSubsetsHelper(int[] nums, int k, int sum, int remainder, int index, boolean[] visited) {
if (remainder == 0) {
remainder = sum;
k--;
}

if (cur >= nums.length()) {
return k == 0;
}

for (int i = index; i < nums.length;i++) {
if (visited[index]) {
return canPartitionKSubsetsHelper(nums, k, sum, remainder, index++, visited);
} else {
if (nums[index] < remainder) {
boolean[] newVisisted = visited[]; // copy without reference
newVisited[index] = true;
return canPartitionKSubsetsHelper(nums, k, sum, remainder - nums[index], index++, newVisited) || canPartitionKSubsetsHelper(nums, k, sum, remainder, index++, visited);
}
}
}
}```