Skip to content

2035. Partition Array Into Two Arrays to Minimize Sum Difference 👍

  • Time: $O(n \cdot 2^{n/2})$
  • Space: $O(2^{n/2})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
 public:
  int minimumDifference(vector<int>& nums) {
    const int n = nums.size() / 2;
    const int sum = accumulate(nums.begin(), nums.end(), 0);
    const int goal = sum / 2;
    const vector<int> lNums(nums.begin(), nums.begin() + n);
    const vector<int> rNums(nums.begin() + n, nums.end());
    int ans = INT_MAX;
    vector<vector<int>> lSums(n + 1);
    vector<vector<int>> rSums(n + 1);

    dfs(lNums, 0, 0, 0, lSums);
    dfs(rNums, 0, 0, 0, rSums);

    for (int lCount = 0; lCount <= n; ++lCount) {
      auto& l = lSums[lCount];
      auto& r = rSums[n - lCount];
      ranges::sort(r);
      for (const int lSum : l) {
        const int i = firstGreaterEqual(r, goal - lSum);
        if (i < r.size()) {
          const int sumPartOne = sum - lSum - r[i];
          const int sumPartTwo = sum - sumPartOne;
          ans = min(ans, abs(sumPartOne - sumPartTwo));
        }
        if (i > 0) {
          const int sumPartOne = sum - lSum - r[i - 1];
          const int sumPartTwo = sum - sumPartOne;
          ans = min(ans, abs(sumPartOne - sumPartTwo));
        }
      }
    }

    return ans;
  }

 private:
  void dfs(const vector<int>& A, int i, int count, int path,
           vector<vector<int>>& sums) {
    if (i == A.size()) {
      sums[count].push_back(path);
      return;
    }
    dfs(A, i + 1, count + 1, path + A[i], sums);
    dfs(A, i + 1, count, path, sums);
  }

  int firstGreaterEqual(const vector<int>& A, int target) {
    return ranges::lower_bound(A, target) - A.begin();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
  public int minimumDifference(int[] nums) {
    final int n = nums.length / 2;
    final int sum = Arrays.stream(nums).sum();
    final int goal = sum / 2;
    final int[] lNums = Arrays.copyOfRange(nums, 0, n);
    final int[] rNums = Arrays.copyOfRange(nums, n, nums.length);
    int ans = Integer.MAX_VALUE;
    List<Integer>[] lSums = new List[n + 1];
    List<Integer>[] rSums = new List[n + 1];

    for (int i = 0; i <= n; ++i) {
      lSums[i] = new ArrayList<>();
      rSums[i] = new ArrayList<>();
    }

    dfs(lNums, 0, 0, 0, lSums);
    dfs(rNums, 0, 0, 0, rSums);

    for (int lCount = 0; lCount <= n; ++lCount) {
      List<Integer> l = lSums[lCount];
      List<Integer> r = rSums[n - lCount];
      Collections.sort(r);
      for (final int lSum : l) {
        final int i = firstGreaterEqual(r, goal - lSum);
        if (i < r.size()) {
          final int sumPartOne = sum - lSum - r.get(i);
          final int sumPartTwo = sum - sumPartOne;
          ans = Math.min(ans, Math.abs(sumPartOne - sumPartTwo));
        }
        if (i > 0) {
          final int sumPartOne = sum - lSum - r.get(i - 1);
          final int sumPartTwo = sum - sumPartOne;
          ans = Math.min(ans, Math.abs(sumPartOne - sumPartTwo));
        }
      }
    }

    return ans;
  }

  private void dfs(int[] A, int i, int count, int path, List<Integer>[] sums) {
    if (i == A.length) {
      sums[count].add(path);
      return;
    }
    dfs(A, i + 1, count + 1, path + A[i], sums);
    dfs(A, i + 1, count, path, sums);
  }

  private int firstGreaterEqual(List<Integer> A, int target) {
    final int i = Collections.binarySearch(A, target);
    return i < 0 ? -i - 1 : i;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
  def minimumDifference(self, nums: List[int]) -> int:
    n = len(nums) // 2
    summ = sum(nums)
    goal = summ // 2
    lNums = nums[:n]
    rNums = nums[n:]
    ans = abs(sum(lNums) - sum(rNums))
    lSums = [[] for _ in range(n + 1)]
    rSums = [[] for _ in range(n + 1)]

    def dfs(A: List[int], i: int, count: int, path: int, sums: List[List[int]]):
      if i == len(A):
        sums[count].append(path)
        return
      dfs(A, i + 1, count + 1, path + A[i], sums)
      dfs(A, i + 1, count, path, sums)

    dfs(lNums, 0, 0, 0, lSums)
    dfs(rNums, 0, 0, 0, rSums)

    for lCount in range(n):
      l = lSums[lCount]
      r = rSums[n - lCount]
      r.sort()
      for lSum in l:
        i = bisect_left(r, goal - lSum)
        if i < len(r):
          sumPartOne = summ - lSum - r[i]
          sumPartTwo = summ - sumPartOne
          ans = min(ans, abs(sumPartOne - sumPartTwo))
        if i > 0:
          sumPartOne = summ - lSum - r[i - 1]
          sumPartTwo = summ - sumPartOne
          ans = min(ans, abs(sumPartOne - sumPartTwo))

    return ans