Recursion-2

groupSum

Question

Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? This is a classic backtracking recursion problem. Once you understand the recursive backtracking strategy in this problem, you can use the same pattern for many problems to search a space of choices. Rather than looking at the whole array, our convention is to consider the part of the array starting at index start and continuing to the end of the array. The caller can specify the whole array simply by passing start as 0. No loops are needed -- the recursive calls progress down the array.

groupSum(0, [2, 4, 8], 10) → true

groupSum(0, [2, 4, 8], 14) → true

groupSum(0, [2, 4, 8], 9) → false

public boolean groupSum(int start, int[] nums, int target) {
  if (start >= nums.length) return (target == 0);

  if (groupSum(start + 1, nums, target - nums[start])) return true;
  if (groupSum(start + 1, nums, target)) return true;
  
  return false;
}

groupSum6

public boolean groupSum6(int start, int[] nums, int target) {
  if (start >= nums.length) return target == 0;
  
  if (nums[start] == 6) {
    if (groupSum6(start + 1, nums, target - nums[start])) return true;
  }
  else {
    if (groupSum6(start + 1, nums, target - nums[start])) return true;
    if (groupSum6(start + 1, nums, target)) return true;
  }
  
  return false;
}

groupNoAdj

public boolean groupNoAdj(int start, int[] nums, int target) {
  if (start >= nums.length) return target == 0;
  
  if (groupNoAdj(start + 2, nums, target - nums[start])) return true;
  if (groupNoAdj(start + 1, nums, target)) return true;
  
  return false;
}

groupSum5

public boolean groupSum5(int start, int[] nums, int target) {
  if (start >= nums.length) return target == 0;
  
  if (nums[start] % 5 == 0) {
    if (start < (nums.length -1) && nums[start + 1] == 1) {
      if (groupSum5(start + 2, nums, target - nums[start])) return true;
    } else {
      if (groupSum5(start + 1, nums, target - nums[start])) return true;
    }
    
  } else {
    if (groupSum5(start + 1, nums, target - nums[start])) return true;
    if (groupSum5(start + 1, nums, target)) return true;
  }
  
  return false;
}

groupSumClump

public boolean groupSumClump(int start, int[] nums, int target) {
  if (start >= nums.length) return target == 0;
  
  if (start < nums.length - 1 && nums[start] == nums[start + 1]) {
    if (groupSumClump(start + 2, nums, target - (2*nums[start]))) return true;
    if (groupSumClump(start + 2, nums, target)) return true;
  } else {
    if (groupSumClump(start + 1, nums, target - nums[start])) return true;
    if (groupSumClump(start + 1, nums, target)) return true;
  }
  
  return false;
}

splitArray

public boolean splitArray(int[] nums) {
  int total = 0;
  
  for (int i = 0; i < nums.length; i++) {
    total += nums[i];
  }
  
  return split(0, nums, 0, total);
}

public boolean split(int idx, int[] nums, int sum, int total) {
  if (nums.length == 0) return true;
  if (idx >= nums.length) return false;
  if (total - sum == sum) return true;
  
  if (split(idx + 1, nums, sum, total)) return true;
  if (split(idx + 1, nums, sum + nums[idx], total)) return true;
  return false;
}

splitOdd10

public boolean splitOdd10(int[] nums) {
  // so that the sum of one group is a multiple of 10
  // and the sum of the other group is odd.
  int total = 0;
  
  for (int i = 0; i < nums.length; i++) {
    total += nums[i];
  }
  
  return dfs(0, total, 0, nums);
}

public boolean dfs(int idx, int total, int sum, int[] nums) {
  if (idx >= nums.length) return false;
  if (nums.length == 0) return false;
  
  int leftSum = total - sum;
  if (sum % 10 == 0  && leftSum % 2 == 1) return true;
  if (leftSum % 10 == 0 && sum % 2 == 1) return true;
  
  if (dfs(idx + 1, total, sum, nums)) return true;
  if (dfs(idx + 1, total, sum + nums[idx], nums)) return true;
  
  return false;
}

split53

• 기존에는 total, sum으로 둬서, total - sum == sum으로 구했다.

• 즉 집합 하나 기준으로 했다면, 이거는 각 집합의 sum을 매번 넘겨주어야 했다.

• 근데 틀렸다.

public boolean split53(int[] nums) {
  
  return dfs(0, 0, 0, nums);
}

public boolean dfs(int idx, int sum3, int sum5, int[] nums) {
  if (nums.length == 0) return true;
  if (idx >= nums.length) return sum3 == sum5;
  // if (sum3 == sum5) return true;
  
  if (nums[idx] % 3 == 0) {
    if (dfs(idx + 1, sum3 + nums[idx], sum5, nums)) 
      return true;
  } else if (nums[idx] % 5 == 0) {
    if (dfs(idx + 1, sum3, sum5 + nums[idx], nums)) 
      return true;
  } else {
    if (dfs(idx + 1, sum3 + nums[idx], sum5, nums)) return true;
    if (dfs(idx + 1, sum3, sum5 + nums[idx], nums)) return true;
  }
  
  return false;
}

• 다른 사람의 코드를 참고했다.

public boolean split53(int[] nums) {
  int index = 0;
  int sum1 = 0;
  int sum2 = 0;
  return recArray(nums, index, sum1, sum2);
}

private boolean recArray ( int[] nums, int index, int sum1, int sum2 ) {
  if ( index >= nums.length ) {
    return sum1 == sum2;
  }

  int value = nums[index];
  if (value%5 == 0)
    return recArray(nums, index + 1, sum1 + value, sum2);
  else if (value%3 == 0)
    return recArray(nums, index + 1, sum1, sum2 + value);
  else    
    return (recArray(nums, index + 1, sum1 + value, sum2) ||
      recArray(nums, index + 1, sum1, sum2 + value));
}