leetcode40：组合总和 II（combination-sum-ii）

[carloscn]

问题描述

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ] 示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]  

提示:

1 <= candidates.length <= 100 1 <= candidates[i] <= 50 1 <= target <= 30

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/combination-sum-ii

[carloscn]

问题分析

使用递归进行搜寻：

//  candidates = [10,1,2,7,6,1,5], target = 8,
static int32_t helper(int64_t *array, size_t len, STACK_T *stack, BUFLIST_T *reslist, size_t k, int64_t target)
{
    int32_t ret = 0;
    int64_t *result_array = NULL;
    size_t result_o_len = 0;
    size_t i = 0;

    UTILS_CHECK_PTR(array);
    UTILS_CHECK_PTR(stack);
    UTILS_CHECK_PTR(reslist);

    stack_print(stack);

    if (k > len - 1) {
        goto finish;
    }

    if (stack_sum(stack) == target) {
        ret = stack_dup_array(stack, &result_array, &result_o_len);
        UTILS_CHECK_RET(ret);
        ret = buflist_append_array(reslist, result_array, result_o_len);
        UTILS_CHECK_RET(ret);
        UTILS_SAFE_FREE(result_array);
        goto finish;
    }

    for (i = k; i < len; i ++) {
        ret = stack_push(stack, array[i]);
        UTILS_CHECK_RET(ret);

        ret = helper(array, len, stack, reslist, i + 1, target);
        UTILS_CHECK_RET(ret);

        ret = stack_pop(stack, NULL);
        UTILS_CHECK_RET(ret);
    }

finish:
    return ret;
}

static int32_t comb_sum(const int64_t *array, size_t len, int64_t target, BUFLIST_T *reslist)
{
    int32_t ret = 0;
    int64_t *dup_array = NULL;
    size_t i = 0;
    STACK_T *stack = NULL;

    UTILS_CHECK_PTR(array);
    UTILS_CHECK_PTR(reslist);
    UTILS_CHECK_LEN(len);

    dup_array = (int64_t *)calloc(sizeof(int64_t), len);
    UTILS_CHECK_PTR(dup_array);

    memcpy(dup_array, array, sizeof(int64_t) * len);

    ret = utils_sort_int64_array(array, len, ORDER_BY_ASCEND);
    UTILS_CHECK_RET(ret);

    stack = stack_malloc(STACK_DEFAULT_SIZE);
    UTILS_CHECK_PTR(stack);

    ret = helper(array, len, stack, reslist, 0, target);
    UTILS_CHECK_RET(ret);

finish:
    stack_free(stack);
    UTILS_SAFE_FREE(dup_array);
    return ret;
}

fn helper(array:&Vec<i64>,
          len:usize,
          stack:&mut Stack<i64>,
          reslist:&mut Vec<Vec<i64>>,
          k:usize,
          target:i64)
{
    if k > len - 1 {
        return;
    }

    stack.print();

    if (stack.sum() == target) {
        let v_c = stack.dup_vector();
        reslist.push(v_c);
        return;
    }

    let mut i:usize = k;

    while i < len {
        stack.push(array[i]);
        helper(array, len, stack, reslist, i + 1, target);
        stack.pop();
        i += 1;
    }
}

fn comb_sum(array:&Vec<i64>, target:i64) -> Vec<Vec<i64>>
{
    let mut reslist:Vec<Vec<i64>> = vec![];
    let mut dup_array:Vec<i64> = array.clone();
    let mut stack:Stack<i64> = Stack::new();

    if 0 == dup_array.len() {
        return reslist;
    }

    dup_array.sort();
    dup_array.reverse();

    helper(array, dup_array.len(), &mut stack, &mut reslist, 0, target);

    // filter_dup_logic()

    println!("the result is {:?}", reslist);

    return reslist;
}

[carloscn]

code

https://github.com/carloscn/structstudy/commit/e1969f344c95d869a1f1360f397fd287744c0898 https://review.gerrithub.io/c/carloscn/structstudy/+/550558