LinkedIn Interview

// 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);
      }
    }
  }
}