找到正整数序列中和为target值的组合

leetcode 39 Combination Sum && Combination Sum II

一、问题描述

给定一组数和一个目标值，找到数字中和为目标值的所有唯一组合。一个数字可以重复选择多次。
注意：
1、所有数字（包括目标）都是正整数。
2、结果集不能包含重复的组合。

【举例】
例1:输入: candidates = [2,3,6,7], target = 7,
输出解集:
[
  [7],
  [2,2,3]

]

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

]

二、解题思路

由于要输出所有解集具体组合而不是解集个数，因此采用dfs的方法，边递归边记录结果

1、当给定的一组数中数字没有重复，如上例给出，可以采用解题算法一

2、当给定的一组数中数字有重复，且一个数字在组合中只能选择一次【如下例】，则采用解题算法二

例1 -- 输入 candidates = [10,1,2,7,6,1,5], target = 8,
输出解集：
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
例2-- 输入 candidates = [2,5,2,1,2], target = 5,
输出解集:
[
  [1,2,2],
  [5]
]

三、解题算法

1、解题算法一---给定数字没有重复的情况

/*********************************************************
Author:tmw
date:2018-5-14
*********************************************************/
#include <stdio.h>
#include <stdlib.h>

/**
    *final_r_perLen ：存储每一组最终结果的长度
    **final_r       ：存储所有结果的数组
    start           : 当前递归起始位置
**/
#define MAX_SIZE 200
int result[MAX_SIZE] = {0}; /**存储中间结果的数组**/
int j=0;                    /**结果数组下标**/
int count = 0;              /**记录所有可能的组合个数**/
void sum_dfs( int* array, int array_len, int sum, int start, int** final_r, int* final_r_perLen )
{
    /**终止条件**/
    if( sum == 0 )
    {
        int i;
        for( i=0; i<j; i++ )
            final_r[count][i] = result[i];

        final_r_perLen[count] = j;
        count++;
        return;
    }

    int k;
    for( k=start; k<array_len; k++ )
    {
        /**收敛条件---剪枝**/
        if( array[k]>sum ) return;

        /**将当前元素加入中间结果数组**/
        result[j++] = array[k];
        sum_dfs(array,array_len,sum-array[k],k,final_r,final_r_perLen);

        j--; /**j回退到递归之前的状态**/
    }
}

/**快排**/
#define swap( x,y,t ) (t=x,x=y,y=t)
int fast_sort_one( int* array, int low, int high )
{
    int target = array[low];
    int temp;
    while( low < high )
    {
        if( low<high && array[high]>=target )
            high--;
        swap(array[low],array[high],temp);
        if( low<high && array[low]<=target )
            low++;
        swap(array[low],array[high],temp);
    }
    return low;
}
void fast_sort_all( int* array, int low, int high )
{
    if( low<high )
    {
        int mid_index = fast_sort_one(array,low,high);
        fast_sort_all(array,low,mid_index-1);
        fast_sort_all(array,mid_index+1,high);
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize)
{
    printf("%dn",candidatesSize);
    fast_sort_all(candidates,0,candidatesSize-1);
    int i;

    int* final_r_perLen = (int*)malloc(MAX_SIZE*sizeof(int));
    int** final_r = (int**)malloc(MAX_SIZE*sizeof(int*));

    for( i=0; i<MAX_SIZE; i++ )
        final_r[i] = (int*)malloc(MAX_SIZE*sizeof(int));

    count = 0; /**全局变量count清零**/
    sum_dfs(candidates,candidatesSize,target,0,final_r,final_r_perLen);

    *columnSizes = (int*)malloc(count*sizeof(int));

    for(i=0; i<count; i++)
        (*columnSizes)[i] = final_r_perLen[i];

    *returnSize = count;

    return final_r;
}

2、解题算法二---给定数字有重复的情况

/************************************************
Author:tmw
date:2018-5-15
************************************************/
#include <stdio.h>
#include <stdlib.h>

/**
【关键点】
1、出现重复元素的处理
2、一个数字在组合中只能选择一次
**/
#define MAX_SIZE 200
int result[MAX_SIZE] = {-1}; //存放中间结果
int j=0;                    //中间结果数组的下标
int count = 0;              //存储一共有多少种组合形式
/**
参数说明：
*array         ： 为有序数组
start          ： 当前递归起始位置
**final_ans    ： 存储所有符合条件的组合情况
*final_perLen  ： 记录每一种组合的元素个数
**/
void sum_dfs( int* array, int array_len, int sum, int start, int** final_ans, int* final_perLen )
{
    printf("sum=%dn",sum);
    /**终止条件**/
    if( sum == 0 )
    {
        int i;
        for( i=0; i<j; i++ )
            final_ans[count][i] = result[i];
        final_perLen[count] = j;
        count++;
        printf("count=%dn",count);
        return;
    }
    int k;
    int previous_num = -1;
    for( k=start; k<array_len; k++ )
    {
        /**剪枝条件**/
        if( sum < array[k] ) return;
        //if( result[j] == array[k] ) continue; //出现重复元素的处理
        if(previous_num == array[k]) continue;

        previous_num = array[k];

        result[j++] = array[k];
        sum_dfs(array,array_len,sum-array[k],k+1,final_ans,final_perLen);
        j--;//j回退
    }
}

/**快排**/
#define swap( x,y,t ) (t=x,x=y,y=t)
int fast_sort_one( int* array, int low, int high )
{
    int target = array[low];
    int temp;
    while( low < high )
    {
        if( low<high && array[high]>=target )
            high--;
        swap(array[low],array[high],temp);
        if( low<high && array[low]<=target )
            low++;
        swap(array[low],array[high],temp);
    }
    return low;
}
void fast_sort_all( int* array, int low, int high )
{
    if( low<high )
    {
        int mid_index = fast_sort_one(array,low,high);
        fast_sort_all(array,low,mid_index-1);
        fast_sort_all(array,mid_index+1,high);
    }
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize)
{
    fast_sort_all(candidates,0,candidatesSize-1);

    int** final_ans = (int**)malloc(MAX_SIZE*sizeof(int*));
    int* final_perLen = (int*)malloc(MAX_SIZE*sizeof(int));
    int i;
    for( i=0; i<MAX_SIZE; i++ )
        final_ans[i] = (int*)malloc(MAX_SIZE*sizeof(int));

    count = 0;//count初始化
    sum_dfs(candidates,candidatesSize,target,0,final_ans,final_perLen);

    printf("count2=%dn",count);

    *columnSizes = (int*)malloc(count*sizeof(int));
    for( i=0; i<count; i++ )
        (*columnSizes)[i] = final_perLen[i];
    *returnSize = count;

    return final_ans;
}

梦想还是要有的，万一实现了呢~~~~ヾ(◍°∇°◍)ﾉﾞ~~~~

最后

以上就是微笑小猫咪最近收集整理的关于找到正整数序列中和为target值的组合的全部内容，更多相关找到正整数序列中和为target值内容请搜索靠谱客的其他文章。