impl Solution {
    fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut results = Vec::new();
        let mut combination = Vec::new();
        Solution::backtrack(&candidates, target, &mut results, &mut combination, 0);
        results
    }

    fn backtrack(
        candidates: &[i32],
        target: i32,
        results: &mut Vec<Vec<i32>>,
        combination: &mut Vec<i32>,
        start_index: usize,
    ) {
        if target == 0 {
            results.push(combination.clone());
            return;
        }

        for i in start_index..candidates.len() {
            if candidates[i] > target {
                // optimization: early stopping
                continue;
            }

            combination.push(candidates[i]);
            Solution::backtrack(candidates, target - candidates[i], results, combination, i); // not i + 1 because we can reuse the same element
            combination.pop(); // backtrack
        }
    }
}