leetcode39：组合总和（combination_sum_39）

carloscn commented 1 year ago

问题分析

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。仅有这两种组合。示例 2：

输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]] 示例 3：

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

提示： 1 <= candidates.length <= 30 2 <= candidates[i] <= 40 candidates 的所有元素互不相同 1 <= target <= 40

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

carloscn commented 1 year ago

问题分析

先生成一个包含所有元素的序列
递归查找满足情况的组合

C语言版本

static void helper(int64_t *array, BUFLIST_T *reslist, STACK_T *stack, size_t k, int64_t target, size_t n)
{
    if (k > n) {
        return;
    }

    stack_print(stack);

    if (stack_sum(stack) == target) {
        int64_t *array = NULL;
        size_t out_len = 0;
        stack_dup_array(stack, &array, &out_len);
        buflist_append_array(reslist, array, out_len);
        UTILS_PRINT_ARRAY(array, out_len, "found : ");
        UTILS_SAFE_FREE(array);
        return;
    }

    stack_push(stack, array[k]);
    helper(array, reslist, stack, k + 1, target, n);
    stack_pop(stack, NULL);
}

static int32_t comb_sum(const int64_t *array, size_t len, int32_t target)
{
    int32_t ret = 0;
    size_t i = 0, j = 0, n = 0;
    STACK_T *stack = NULL;
    BUFLIST_T *buflist = NULL;
    int64_t dup_array[1024];
    int64_t e = 0;
    int64_t sum = 0;

    UTILS_CHECK_PTR(array);
    UTILS_CHECK_LEN(len);

    for (i = 0; i < len; i ++) {
        sum = 0;
        e = array[i];
        do {
            dup_array[j] = e;
            sum += e;
            j ++;
        } while (sum < target);
    }
    len = j;

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

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

    buflist = buflist_malloc();
    UTILS_CHECK_PTR(buflist);

    for (i = 0; i < len; i ++) {
        helper(dup_array, buflist, stack, i, target, len);
    }

    LOG("the result is : \n");
    buflist_infolog(buflist);

finish:
    stack_free(stack);
    buflist_free(buflist);
    return ret;
}

Rust版本

fn helper(array:&Vec<i64>, reslist:&mut Vec<Vec<i64>>, stack:&mut Stack<i64>, k:usize, target:i64, n:usize)
{
    if k > n {
        return;
    }
    //stack.print();

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

    stack.push(array[k]);
    helper(array, reslist, stack, k + 1, target, n);
    stack.pop();
}

fn comb_sum(array:&Vec<i64>, target:i64) -> Vec<Vec<i64>>
{
    let mut reslist:Vec<Vec<i64>> = vec![];
    let mut dup_array:Vec<i64> = vec![];
    let mut i:usize = 0;
    let mut sum:i64;
    let mut j:usize = 0;
    let mut e:&i64;
    let mut stack:Stack<i64> = Stack::new();

    while i < array.len() {
        sum = 0;
        e = &array[i];
        while sum < target {
            dup_array.push(*e);
            sum += *e;
            j += 1;
        }
        i += 1;
    }

    i = 0;
    dup_array.sort();
    dup_array.push(0);

    while i < dup_array.len() - 1 {
        helper(&dup_array, &mut reslist, &mut stack, i, target, dup_array.len() - 1);
        i += 1;
    }

    return reslist;
}

carloscn commented 1 year ago

code

https://github.com/carloscn/structstudy/commit/598c28f95716ea25a91c3bb928b9a5db92336dee https://review.gerrithub.io/c/carloscn/structstudy/+/550542

carloscn / structstudy