Twitter | OA 2019 | Get Set Go

image

image

PS: Weirdly - noniterative DP solution won't work - I guess it's because of using a large size array for sum.

My Solution
  static boolean isSubsetSum(Integer set[], 
                            int n, int sum) 
    { 
        // Base Cases 
        if (sum == 0) 
            return true; 
        if (n == 0 && sum != 0) 
            return false; 
         
        if (set[n-1] > sum) 
            return isSubsetSum(set, n-1, sum); 
        return isSubsetSum(set, n-1, sum) ||  
            isSubsetSum(set, n-1, sum-set[n-1]); 
    } 
    public static boolean isPossible(List<Integer> calCounts, int requiredCals) {
        Integer[] array = new Integer[calCounts.size()];
        calCounts.toArray(array); 
        return isSubsetSum(array, calCounts.size(), requiredCals);
    }
Comments (8)