216.组合总和III

链接：. - 力扣（LeetCode）

题目描述：

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

思路：

因为是求组合问题，所以使用回溯算法来实现，当出现符合我们要求的结果时，则进行收集，不断进行向下递归

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
//存储单个满足条件的结果
int *path;
int pathtop;
//存储所有的结果
int **result;
int resulttop;

void backtracking(int target, int k , int sum, int startindex)
{
    if(pathtop == k)
    {
        if(sum == target)
        {
            int *temp = (int *)malloc(sizeof(int) * k);
            for(int i = 0 ; i < k ; i++)
                temp[i] = path[i];
            result[resulttop++] = temp;
        }
        return;
    }

    for(int i = startindex; i <= 9; i++)
    {
        sum += i;
        path[pathtop++] = i;
        backtracking(target,k,sum,i+1);
        sum -= i;
        pathtop--;
    }
}

int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {
    path = (int *)malloc(sizeof(int) * k);
    result = (int **)malloc(sizeof(int *) * 1000);
    pathtop = resulttop = 0;

    backtracking(n, k, 0, 1);
    *returnSize = resulttop;

    *returnColumnSizes = (int *)malloc(sizeof(int) * resulttop);
    for(int i = 0; i < resulttop ; i++)
        (*returnColumnSizes)[i] = k;
    
    return result;
}

剪枝操作：

当我们遍历到的值已经大于我们的目标值时，我们可以直接进行回溯，而不需要再进行遍历

只需要的判断if(pathtop == k)之前进行剪枝，即加上下面的代码

if(sum > target)
        return ;

如果当前的元素总和已经超出我们需要的返回，直接就可以进行回溯

 

17.电话号码的字母组合

链接：. - 力扣（LeetCode）

题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

 

思路：

因为是求组合问题，因此可以使用回溯算法解决，我们以题目的示例1为例，将其抽象为一颗树形的结构，即如下所示

我们可以根据抽象的树形结构可知，符合要求的组合的长度与题目传入的字符串的长度一致，并且我们可以将题目给出的数字映射到一个数组中，数组的下标就是对应的数字，存储的值就是数字对应的字符串，for循环就是横向遍历，而递归是纵向遍历

代码实现：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

//将字符进行映射
char map[10][5] = {"\0","\0","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//存放单个组合
char *path;
int pathtop;
//存放所有的组合
char **result;
int resulttop;

//传入的参数为题目提供的字符串，遍历到字符串的位置
void backtracking(char *digits, int index)
{
    //如果字符串已经遍历完成
    if(index == strlen(digits))
    {
        //开辟数组，用来复制path的值，数组的大小应该为digits的长度+1
        //digits数组的长度就是每个子集中元素的个数，+1是存放'\0'
        char *temp = (char *)malloc(sizeof(char) * strlen(digits) + 1);
        //复制path数组
        for(int i = 0; i < strlen(digits); i++)
            temp[i] = path[i];
        //末尾位置加上'\0'
        temp[strlen(digits)] = '\0';
        //将符合条件的组合存入结果集中
        result[resulttop++] = temp;

        return ;  
    }
    //找出digits数组中当前遍历位置对应的字符并转化为数字
    int digit = digits[index] - '0';
    //通过数字找到映射数组中存储的字符串
    char *p = map[digit];
    //字符串不空
    for(int i = 0; i < strlen(p) ;i++)
    {
        //取出元素存放到组合中
        path[pathtop++] = p[i];
        //向下遍历，遍历的是下一个数字在map数组中对应的字符串
        backtracking(digits,index+1);
        //回溯
        pathtop--;
    }
}

char** letterCombinations(char* digits, int* returnSize) {
    path = malloc(sizeof(char) * strlen(digits) + 1);
    result = (char **)malloc(sizeof(char *) * 300);

    *returnSize = 0;
    if(strlen(digits) == 0)
        return result;
    
    pathtop = resulttop = 0;
    backtracking(digits,0);
    *returnSize = resulttop;

    return result;
}