-
Notifications
You must be signed in to change notification settings - Fork 0
/
mod.rs
57 lines (49 loc) · 1.35 KB
/
mod.rs
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
pub struct Solution;
impl Solution {
pub fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
fn dfs(result: &mut Vec<Vec<i32>>, path: &mut Vec<i32>, candidates: &[i32], target: i32) {
if target < 0 {
return;
}
if target == 0 {
result.push(path.clone());
return;
}
for i in 0..candidates.len() {
if candidates[i] > target {
break;
}
path.push(candidates[i]);
dfs(result, path, &candidates[i..], target - candidates[i]);
path.pop();
}
}
candidates.sort_unstable();
let mut result = vec![];
dfs(&mut result, &mut vec![], &candidates, target);
result
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::vec_vec;
#[test]
fn test1() {
assert_eq!(
Solution::combination_sum(vec![2, 3, 6, 7], 7),
vec_vec![[2, 2, 3], [7]]
);
}
#[test]
fn test2() {
assert_eq!(
Solution::combination_sum(vec![2, 3, 5], 8),
vec_vec![[2, 2, 2, 2], [2, 3, 3], [3, 5]]
);
}
#[test]
fn test3() {
assert_eq!(Solution::combination_sum(vec![2], 1), [] as [[i32; 0]; 0]);
}
}