Not a subset sum

JavaView on GFG

Problem Overview

Find smallest positive number that cannot be represented as sum of any subset of array.

Intuition

Find smallest positive number that cannot be represented as sum of any subset of array.

Algorithm

1Sort array. Maintain reach=0. For each element: if arr[i] <= reach+1: reach += arr[i]. Else break. Answer = reach+1.

Common Pitfalls

• Greedy: if sorted arr[i] <= reach+1, then all values 1..reach+arr[i] are reachable. O(n log n).

Not a subset sum.java

Java

import java.util.Arrays;

// Approach: Sort array. Track the smallest sum not expressible. If arr[i] > reach+1, return reach+1.
// Time: O(n log n) Space: O(1)
class Solution {
    public long findSmallest(int[] arr) {
        int res = 1;
        for (int i = 0; i <= arr.length - 1; i++) {
            // checking the first elemant is less than res
            if (res < arr[0])
                return res;
            // checking if arr[i] is greater thn res then we cannot add
            if (arr[i] > res)
                break;
            else // checking the number is present or not if present than add
                res = res + arr[i];
        }

        return res;
    }
}

//Version 2:
class Solution1 {
    public int findSmallest(int[] arr) {
        Arrays.sort(arr);

        long res = 1;

        for (int num : arr) {
            if (num > res) {
                break;
            }
            res += num;
        }

        return (int) res;
    }
}

Was this solution helpful?