YSMull
<-- algorithm



原题链接

2021/04/05

题目描述

给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。

candidates中的数字可以无限制重复被选取。

分析

比较简单的搜索，需要注意通过限制结果是升序的来去重。

实现

impl Solution {
    pub fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result = vec![];
        candidates.sort();
        Solution::combination_sum0(&candidates, target, &mut vec![], &mut result);
        return result;
    }

    fn combination_sum0(candidates: &Vec<i32>, target: i32, cur: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        if target == 0 {
            result.push(cur.clone());
            return;
        }
        let filter: Vec<_> = candidates.iter().filter(|i| {
            return if let Some(l) = cur.last() {
                i <= &&target && i >= &l
            } else {
                i <= &&target
            }
        }).collect();
        for it in filter {
            cur.push(*it);
            Solution::combination_sum0(candidates, target - *it, cur, result);
            cur.pop();
        }
    }
}