39. Combination Sum Medium

1/**
2 * [39] Combination Sum
3 *
4 * Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
5 * The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
6 * It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
7 *  
8 * Example 1:
9 * 
10 * Input: candidates = [2,3,6,7], target = 7
11 * Output: [[2,2,3],[7]]
12 * Explanation:
13 * 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
14 * 7 is a candidate, and 7 = 7.
15 * These are the only two combinations.
16 * 
17 * Example 2:
18 * 
19 * Input: candidates = [2,3,5], target = 8
20 * Output: [[2,2,2,2],[2,3,3],[3,5]]
21 * 
22 * Example 3:
23 * 
24 * Input: candidates = [2], target = 1
25 * Output: []
26 * 
27 *  
28 * Constraints:
29 * 
30 * 1 <= candidates.length <= 30
31 * 1 <= candidates[i] <= 200
32 * All elements of candidates are distinct.
33 * 1 <= target <= 500
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/combination-sum/
39// discuss: https://leetcode.com/problems/combination-sum/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42use std::collections::HashSet;
43impl Solution {
44    pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
45        let mut result: HashSet<Vec<i32>> = HashSet::new();
46        Self::dfs(&candidates, target, &mut vec![], 0, &mut result);
47        result.into_iter().collect()
48    }
49
50    fn dfs(candidates: &Vec<i32>, remain: i32, current: &mut Vec<i32>, index: usize, result: &mut HashSet<Vec<i32>>) {
51        if remain == 0 {
52            let mut s = current.clone();
53            s.sort();
54            result.insert(s);
55            return;
56        } else if remain < 0 {
57            return;
58        }
59
60        for i in index..candidates.len() {
61            current.push(candidates[i]);
62            Self::dfs(candidates, remain - candidates[i], current, i, result);
63            current.pop();
64        }
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_39() {
76        println!("Got {:#?}", Solution::combination_sum(vec![100,200,4,12], 400));
77    }
78}
79