Array
Backtracking
Math
Description
You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.
You are restricted with the following rules:
The division operator '/' represents real division, not integer division.
For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.
For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed .
You cannot concatenate numbers together
For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.
Return true if you can get such expression that evaluates to 24, and false otherwise.
Example 1:
Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24
Example 2:
Input: cards = [1,2,1,2]
Output: false
Constraints:
cards.length == 41 <= cards[i] <= 9
Solutions
Solution 1: DFS
We design a function \(dfs(nums)\) , where \(nums\) represents the current number sequence. The function returns a boolean value indicating whether there exists a permutation that makes this number sequence equal to \(24\) .
If the length of \(nums\) is \(1\) , we return \(true\) only when this number is \(24\) , otherwise we return \(false\) .
Otherwise, we can enumerate any two numbers \(a\) and \(b\) in \(nums\) as the left and right operands, and enumerate the operator \(op\) between \(a\) and \(b\) . The result of \(a\ op\ b\) can be used as an element of the new number sequence. We add it to the new number sequence and remove \(a\) and \(b\) from \(nums\) , then recursively call the \(dfs\) function. If it returns \(true\) , it means we have found a permutation that makes this number sequence equal to \(24\) , and we return \(true\) .
If none of the enumerated cases return \(true\) , we return \(false\) .
Python3 Java C++ Go TypeScript Rust
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 judgePoint24 ( self , cards : List [ int ]) -> bool :
def dfs ( nums : List [ float ]):
n = len ( nums )
if n == 1 :
if abs ( nums [ 0 ] - 24 ) < 1e-6 :
return True
return False
ok = False
for i in range ( n ):
for j in range ( n ):
if i != j :
nxt = [ nums [ k ] for k in range ( n ) if k != i and k != j ]
for op in ops :
match op :
case "/" :
if nums [ j ] == 0 :
continue
ok |= dfs ( nxt + [ nums [ i ] / nums [ j ]])
case "*" :
ok |= dfs ( nxt + [ nums [ i ] * nums [ j ]])
case "+" :
ok |= dfs ( nxt + [ nums [ i ] + nums [ j ]])
case "-" :
ok |= dfs ( nxt + [ nums [ i ] - nums [ j ]])
if ok :
return True
return ok
ops = ( "+" , "-" , "*" , "/" )
nums = [ float ( x ) for x in cards ]
return dfs ( nums )
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
56 class Solution {
private final char [] ops = { '+' , '-' , '*' , '/' };
public boolean judgePoint24 ( int [] cards ) {
List < Double > nums = new ArrayList <> ();
for ( int num : cards ) {
nums . add (( double ) num );
}
return dfs ( nums );
}
private boolean dfs ( List < Double > nums ) {
int n = nums . size ();
if ( n == 1 ) {
return Math . abs ( nums . get ( 0 ) - 24 ) < 1e-6 ;
}
boolean ok = false ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( i != j ) {
List < Double > nxt = new ArrayList <> ();
for ( int k = 0 ; k < n ; ++ k ) {
if ( k != i && k != j ) {
nxt . add ( nums . get ( k ));
}
}
for ( char op : ops ) {
switch ( op ) {
case '/' -> {
if ( nums . get ( j ) == 0 ) {
continue ;
}
nxt . add ( nums . get ( i ) / nums . get ( j ));
}
case '*' -> {
nxt . add ( nums . get ( i ) * nums . get ( j ));
}
case '+' -> {
nxt . add ( nums . get ( i ) + nums . get ( j ));
}
case '-' -> {
nxt . add ( nums . get ( i ) - nums . get ( j ));
}
}
ok |= dfs ( nxt );
if ( ok ) {
return true ;
}
nxt . remove ( nxt . size () - 1 );
}
}
}
}
return ok ;
}
}
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
56
57
58 class Solution {
public :
bool judgePoint24 ( vector < int >& cards ) {
vector < double > nums ;
for ( int num : cards ) {
nums . push_back ( static_cast < double > ( num ));
}
return dfs ( nums );
}
private :
const char ops [ 4 ] = { '+' , '-' , '*' , '/' };
bool dfs ( vector < double >& nums ) {
int n = nums . size ();
if ( n == 1 ) {
return abs ( nums [ 0 ] - 24 ) < 1e-6 ;
}
bool ok = false ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( i != j ) {
vector < double > nxt ;
for ( int k = 0 ; k < n ; ++ k ) {
if ( k != i && k != j ) {
nxt . push_back ( nums [ k ]);
}
}
for ( char op : ops ) {
switch ( op ) {
case '/' :
if ( nums [ j ] == 0 ) {
continue ;
}
nxt . push_back ( nums [ i ] / nums [ j ]);
break ;
case '*' :
nxt . push_back ( nums [ i ] * nums [ j ]);
break ;
case '+' :
nxt . push_back ( nums [ i ] + nums [ j ]);
break ;
case '-' :
nxt . push_back ( nums [ i ] - nums [ j ]);
break ;
}
ok |= dfs ( nxt );
if ( ok ) {
return true ;
}
nxt . pop_back ();
}
}
}
}
return ok ;
}
};
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 func judgePoint24 ( cards [] int ) bool {
ops := [ 4 ] rune { '+' , '-' , '*' , '/' }
nums := make ([] float64 , len ( cards ))
for i , num := range cards {
nums [ i ] = float64 ( num )
}
var dfs func ([] float64 ) bool
dfs = func ( nums [] float64 ) bool {
n := len ( nums )
if n == 1 {
return math . Abs ( nums [ 0 ] - 24 ) < 1e-6
}
ok := false
for i := 0 ; i < n ; i ++ {
for j := 0 ; j < n ; j ++ {
if i != j {
var nxt [] float64
for k := 0 ; k < n ; k ++ {
if k != i && k != j {
nxt = append ( nxt , nums [ k ])
}
}
for _ , op := range ops {
switch op {
case '/' :
if nums [ j ] == 0 {
continue
}
nxt = append ( nxt , nums [ i ] / nums [ j ])
case '*' :
nxt = append ( nxt , nums [ i ] * nums [ j ])
case '+' :
nxt = append ( nxt , nums [ i ] + nums [ j ])
case '-' :
nxt = append ( nxt , nums [ i ] - nums [ j ])
}
ok = ok || dfs ( nxt )
if ok {
return true
}
nxt = nxt [: len ( nxt ) - 1 ]
}
}
}
}
return ok
}
return dfs ( nums )
}
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 function judgePoint24 ( cards : number []) : boolean {
const ops : string [] = [ '+' , '-' , '*' , '/' ];
const dfs = ( nums : number []) : boolean => {
const n : number = nums . length ;
if ( n === 1 ) {
return Math . abs ( nums [ 0 ] - 24 ) < 1e-6 ;
}
let ok : boolean = false ;
for ( let i = 0 ; i < n ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
if ( i !== j ) {
const nxt : number [] = [];
for ( let k = 0 ; k < n ; k ++ ) {
if ( k !== i && k !== j ) {
nxt . push ( nums [ k ]);
}
}
for ( const op of ops ) {
switch ( op ) {
case '/' :
if ( nums [ j ] === 0 ) {
continue ;
}
nxt . push ( nums [ i ] / nums [ j ]);
break ;
case '*' :
nxt . push ( nums [ i ] * nums [ j ]);
break ;
case '+' :
nxt . push ( nums [ i ] + nums [ j ]);
break ;
case '-' :
nxt . push ( nums [ i ] - nums [ j ]);
break ;
}
ok = ok || dfs ( nxt );
if ( ok ) {
return true ;
}
nxt . pop ();
}
}
}
}
return ok ;
};
return dfs ( cards );
}
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 impl Solution {
pub fn judge_point24 ( cards : Vec < i32 > ) -> bool {
fn dfs ( nums : Vec < f64 > ) -> bool {
let n = nums . len ();
if n == 1 {
return ( nums [ 0 ] - 24.0 ). abs () < 1e-6 ;
}
for i in 0 .. n {
for j in 0 .. n {
if i == j {
continue ;
}
let mut nxt = Vec :: new ();
for k in 0 .. n {
if k != i && k != j {
nxt . push ( nums [ k ]);
}
}
for op in 0 .. 4 {
let mut nxt2 = nxt . clone ();
match op {
0 => {
nxt2 . push ( nums [ i ] + nums [ j ]);
}
1 => {
nxt2 . push ( nums [ i ] - nums [ j ]);
}
2 => {
nxt2 . push ( nums [ i ] * nums [ j ]);
}
3 => {
if nums [ j ]. abs () < 1e-6 {
continue ;
}
nxt2 . push ( nums [ i ] / nums [ j ]);
}
_ => {}
}
if dfs ( nxt2 ) {
return true ;
}
}
}
}
false
}
let nums : Vec < f64 > = cards . into_iter (). map ( | x | x as f64 ). collect ();
dfs ( nums )
}
}
GitHub
