Bit Manipulation
Array
Two Pointers
Dynamic Programming
Bitmask
Description
You are given an integer array nums
and an integer goal
.
You want to choose a subsequence of nums
such that the sum of its elements is the closest possible to goal
. That is, if the sum of the subsequence's elements is sum
, then you want to minimize the absolute difference abs(sum - goal)
.
Return the minimum possible value of abs(sum - goal)
.
Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.
Example 1:
Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.
Example 2:
Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: Choose the subsequence [7,-9,-2], with a sum of -4.
The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.
Example 3:
Input: nums = [1,2,3], goal = -7
Output: 7
Constraints:
1 <= nums.length <= 40
-107 <= nums[i] <= 107
-109 <= goal <= 109
Solutions
Solution 1
Python3 Java C++ Go
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 class Solution :
def minAbsDifference ( self , nums : List [ int ], goal : int ) -> int :
n = len ( nums )
left = set ()
right = set ()
self . getSubSeqSum ( 0 , 0 , nums [: n // 2 ], left )
self . getSubSeqSum ( 0 , 0 , nums [ n // 2 :], right )
result = inf
right = sorted ( right )
rl = len ( right )
for l in left :
remaining = goal - l
idx = bisect_left ( right , remaining )
if idx < rl :
result = min ( result , abs ( remaining - right [ idx ]))
if idx > 0 :
result = min ( result , abs ( remaining - right [ idx - 1 ]))
return result
def getSubSeqSum ( self , i : int , curr : int , arr : List [ int ], result : Set [ int ]):
if i == len ( arr ):
result . add ( curr )
return
self . getSubSeqSum ( i + 1 , curr , arr , result )
self . getSubSeqSum ( i + 1 , curr + arr [ i ], arr , result )
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 class Solution {
public int minAbsDifference ( int [] nums , int goal ) {
int n = nums . length ;
List < Integer > lsum = new ArrayList <> ();
List < Integer > rsum = new ArrayList <> ();
dfs ( nums , lsum , 0 , n / 2 , 0 );
dfs ( nums , rsum , n / 2 , n , 0 );
rsum . sort ( Integer :: compareTo );
int res = Integer . MAX_VALUE ;
for ( Integer x : lsum ) {
int target = goal - x ;
int left = 0 , right = rsum . size ();
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
if ( rsum . get ( mid ) < target ) {
left = mid + 1 ;
} else {
right = mid ;
}
}
if ( left < rsum . size ()) {
res = Math . min ( res , Math . abs ( target - rsum . get ( left )));
}
if ( left > 0 ) {
res = Math . min ( res , Math . abs ( target - rsum . get ( left - 1 )));
}
}
return res ;
}
private void dfs ( int [] nums , List < Integer > sum , int i , int n , int cur ) {
if ( i == n ) {
sum . add ( cur );
return ;
}
dfs ( nums , sum , i + 1 , n , cur );
dfs ( nums , sum , i + 1 , n , cur + nums [ 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
38
39
40
41
42
43
44
45 class Solution {
public :
int minAbsDifference ( vector < int >& nums , int goal ) {
int n = nums . size ();
vector < int > lsum ;
vector < int > rsum ;
dfs ( nums , lsum , 0 , n / 2 , 0 );
dfs ( nums , rsum , n / 2 , n , 0 );
sort ( rsum . begin (), rsum . end ());
int res = INT_MAX ;
for ( int x : lsum ) {
int target = goal - x ;
int left = 0 , right = rsum . size ();
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
if ( rsum [ mid ] < target ) {
left = mid + 1 ;
} else {
right = mid ;
}
}
if ( left < rsum . size ()) {
res = min ( res , abs ( target - rsum [ left ]));
}
if ( left > 0 ) {
res = min ( res , abs ( target - rsum [ left - 1 ]));
}
}
return res ;
}
private :
void dfs ( vector < int >& nums , vector < int >& sum , int i , int n , int cur ) {
if ( i == n ) {
sum . emplace_back ( cur );
return ;
}
dfs ( nums , sum , i + 1 , n , cur );
dfs ( nums , sum , i + 1 , n , cur + nums [ 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
38
39
40
41
42
43
44
45
46
47
48
49 func minAbsDifference ( nums [] int , goal int ) int {
n := len ( nums )
lsum := make ([] int , 0 )
rsum := make ([] int , 0 )
dfs ( nums [: n / 2 ], & lsum , 0 , 0 )
dfs ( nums [ n / 2 :], & rsum , 0 , 0 )
sort . Ints ( rsum )
res := math . MaxInt32
for _ , x := range lsum {
t := goal - x
l , r := 0 , len ( rsum )
for l < r {
m := int ( uint ( l + r ) >> 1 )
if rsum [ m ] < t {
l = m + 1
} else {
r = m
}
}
if l < len ( rsum ) {
res = min ( res , abs ( t - rsum [ l ]))
}
if l > 0 {
res = min ( res , abs ( t - rsum [ l - 1 ]))
}
}
return res
}
func dfs ( nums [] int , sum * [] int , i , cur int ) {
if i == len ( nums ) {
* sum = append ( * sum , cur )
return
}
dfs ( nums , sum , i + 1 , cur )
dfs ( nums , sum , i + 1 , cur + nums [ i ])
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution :
def minAbsDifference ( self , nums : List [ int ], goal : int ) -> int :
def dfs ( arr , res , i , s ):
if i == len ( arr ):
res . add ( s )
return
dfs ( arr , res , i + 1 , s )
dfs ( arr , res , i + 1 , s + arr [ i ])
n = len ( nums )
left , right = set (), set ()
dfs ( nums [: n >> 1 ], left , 0 , 0 )
dfs ( nums [ n >> 1 :], right , 0 , 0 )
right = sorted ( right )
ans = inf
for l in left :
x = goal - l
i = bisect_left ( right , x )
if i < len ( right ):
ans = min ( ans , abs ( x - right [ i ]))
if i :
ans = min ( ans , abs ( x - right [ i - 1 ]))
return ans
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 class Solution {
public int minAbsDifference ( int [] nums , int goal ) {
int n = nums . length ;
Set < Integer > left = new HashSet <> ();
Set < Integer > right = new HashSet <> ();
dfs ( nums , 0 , n >> 1 , 0 , left );
dfs ( nums , n >> 1 , n , 0 , right );
List < Integer > rs = new ArrayList <> ( right );
Collections . sort ( rs );
int ans = Integer . MAX_VALUE ;
for ( int x : left ) {
int y = goal - x ;
int l = 0 , r = rs . size ();
while ( l < r ) {
int mid = ( l + r ) >> 1 ;
if ( rs . get ( mid ) >= y ) {
r = mid ;
} else {
l = mid + 1 ;
}
}
if ( l < rs . size ()) {
ans = Math . min ( ans , Math . abs ( y - rs . get ( l )));
}
if ( l > 0 ) {
ans = Math . min ( ans , Math . abs ( y - rs . get ( l - 1 )));
}
}
return ans ;
}
private void dfs ( int [] arr , int i , int n , int s , Set < Integer > res ) {
if ( i == n ) {
res . add ( s );
return ;
}
dfs ( arr , i + 1 , n , s , res );
dfs ( arr , i + 1 , n , s + arr [ i ] , res );
}
}
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 class Solution {
public :
int minAbsDifference ( vector < int >& nums , int goal ) {
int n = nums . size ();
vector < int > left ;
vector < int > right ;
dfs ( nums , left , 0 , n >> 1 , 0 );
dfs ( nums , right , n >> 1 , n , 0 );
sort ( right . begin (), right . end ());
int ans = INT_MAX ;
for ( int x : left ) {
int y = goal - x ;
int idx = lower_bound ( right . begin (), right . end (), y ) - right . begin ();
if ( idx < right . size ()) ans = min ( ans , abs ( y - right [ idx ]));
if ( idx ) ans = min ( ans , abs ( y - right [ idx - 1 ]));
}
return ans ;
}
private :
void dfs ( vector < int >& arr , vector < int >& res , int i , int n , int s ) {
if ( i == n ) {
res . emplace_back ( s );
return ;
}
dfs ( arr , res , i + 1 , n , s );
dfs ( arr , res , i + 1 , n , s + arr [ 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
38
39
40
41
42
43
44 func minAbsDifference ( nums [] int , goal int ) int {
n := len ( nums )
left := [] int {}
right := [] int {}
dfs ( nums [: n >> 1 ], & left , 0 , 0 )
dfs ( nums [ n >> 1 :], & right , 0 , 0 )
sort . Ints ( right )
ans := math . MaxInt32
for _ , x := range left {
y := goal - x
l , r := 0 , len ( right )
for l < r {
mid := ( l + r ) >> 1
if right [ mid ] >= y {
r = mid
} else {
l = mid + 1
}
}
if l < len ( right ) {
ans = min ( ans , abs ( y - right [ l ]))
}
if l > 0 {
ans = min ( ans , abs ( y - right [ l - 1 ]))
}
}
return ans
}
func dfs ( arr [] int , res * [] int , i , s int ) {
if i == len ( arr ) {
* res = append ( * res , s )
return
}
dfs ( arr , res , i + 1 , s )
dfs ( arr , res , i + 1 , s + arr [ i ])
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}