40. Combination Sum II Medium

1/**
2 * [40] Combination Sum II
3 *
4 * Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
5 * Each number in candidates may only be used once in the combination.
6 * Note: The solution set must not contain duplicate combinations.
7 *  
8 * Example 1:
9 * 
10 * Input: candidates = [10,1,2,7,6,1,5], target = 8
11 * Output: 
12 * [
13 * [1,1,6],
14 * [1,2,5],
15 * [1,7],
16 * [2,6]
17 * ]
18 * 
19 * Example 2:
20 * 
21 * Input: candidates = [2,5,2,1,2], target = 5
22 * Output: 
23 * [
24 * [1,2,2],
25 * [5]
26 * ]
27 * 
28 *  
29 * Constraints:
30 * 
31 * 1 <= candidates.length <= 100
32 * 1 <= candidates[i] <= 50
33 * 1 <= target <= 30
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/combination-sum-ii/
39// discuss: https://leetcode.com/problems/combination-sum-ii/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42impl Solution {
43    pub fn combination_sum2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
44        let mut result: Vec<Vec<i32>> = Vec::new();
45        let mut all = candidates.clone();
46        all.sort();
47        Self::dfs(&all, target, &mut vec![], 0, &mut result);
48        result.into_iter().collect()
49    }
50
51    fn dfs(candidates: &Vec<i32>, remain: i32, current: &mut Vec<i32>, index: usize, result: &mut Vec<Vec<i32>>) {
52        if remain == 0 {
53            result.push(current.clone());
54            return;
55        } else if remain < 0 {
56            return;
57        }
58
59        for i in index..candidates.len() {
60            if i > index && candidates[i] == candidates[i - 1] {
61                continue;
62            }
63            current.push(candidates[i]);
64            Self::dfs(candidates, remain - candidates[i], current, i + 1, result);
65            current.pop();
66        }
67    }
68}
69
70// submission codes end
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test_40() {
78        println!("Got {:#?}", Solution::combination_sum2(vec![2,5,2,1,2], 5));
79    }
80}
81