• 算法之回溯

    在这里插入图片描述

    • 我最近开了几个专栏，诚信互三！
      ====> |||《算法专栏》：：刷题教程来自网站《代码随想录》。|||
      ====> |||《C++专栏》：：记录我学习C++的经历，看完你一定会有收获。|||
      ====> |||《Linux专栏》：：记录我学习Linux的经历，看完你一定会有收获。|||
      ====> |||《C#专栏》：：记录我复习C#的经历，深度理解，查漏补缺，不定期更新。|||

    回溯算法

    什么是回溯

    回溯是一种暴力搜索的算法，回溯算法通过循环控制树的宽度，递归调用控制树的深度，来收集满足条件的集合。

    回溯算法能解决什么问题

    1.排列组合
    2.组合总和
    3.分割字串
    4.子集

    回溯算法经典OJ

    1.排列组合问题

    组合问题的分析：组合及每层选的值以及该值的左边所有值下一层则不能在被选择，为了控制选值，则需要startIndex来索引下标，并根据条件收集和返回结果。
    排列问题的分析：排列问题每层都可以取除了上一层选择的值之外的所有值，所以一般不需要startIndex控制索引，而需要hash表记住上一层所选择的值。
    剪枝：剪枝操作要根据题目的收集结果条件进行剪枝，一般都在for循环的判断部分进行剪枝。

    组合
    给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

    你可以按 任何顺序 返回答案。

    问题分析：该题要求返回组合，则需要startIndex控制索引防止重复选取，同时返回条件是当收集到2个结果返回。

    int* result;// - 结果数组
int arrTop;// - 控制返回数组的下标
int top;// - 控制结果数组的下标
int** arr;// - 结果数组

void BackTracking(int n, int k, int** arr, int index)
{
    if(top == k)// - 满足条件返回
    {
        int* tmp = (int*)malloc(sizeof(int)*k);
        for(int i = 0; i < k; i++)
        {
            tmp[i] = result[i];
        }
        arr[arrTop++] = tmp;
        return;

    }
    for(int i = index; i <= n; i++)
    {
        result[top++] = i;
        BackTracking(n,k,arr,i+1);
        // - 回溯
        top--;
    }

}



int** combine(int n, int k, int* returnSize, int** returnColumnSizes) 
{
        arr = (int**)malloc(sizeof(int*)*10000);
        result = (int*)malloc(sizeof(int)*k);

        arrTop = top = 0;
        BackTracking(n,k,arr,1);
        *returnSize = arrTop;// - 返回arr数组有多少行

        *returnColumnSizes = (int*)malloc(sizeof(int)*(*returnSize));// - 返回arr数组每列有多少个元素。
        for(int i = 0; i < *returnSize; i++)
        {
            (*returnColumnSizes)[i] = k;

        }
        return arr;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    剪枝：本题要求收集到k个值就返回，若接下来收集的元素最大值都收集不到k个，则就不用遍历了。
    result数组中有Top个元素，所需需要的元素个数为: k - Top;
    列表中剩余元素（n-i） >= 所需需要的元素个数（k - Top)
    在集合n中至多要从该起始位置 : i <= n - (k - Top) + 1，开始遍历

     for(int i = index; i <= n - (k-Top)+1; i++)

    • 1

    全排列

    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

    问题分析：不含重复数子，则代表不存在两个结果相同，但是所对应的下标不同，则不需要在每层去重，要返回全排列，返回条件就是rTop的值是numsSize，并且该问题为排列问题，可以重选。

    int* path;
int pathTop;
int** ans;
int ansTop;

//将used中元素都设置为0
void initialize(int* used, int usedLength) {
    int i;
    for(i = 0; i < usedLength; i++) {
        used[i] = 0;
    }
}

//将path中元素拷贝到ans中
void copy() {
    int* tempPath = (int*)malloc(sizeof(int) * pathTop);
    int i;
    for(i = 0; i < pathTop; i++) {
        tempPath[i] = path[i];
    }
    ans[ansTop++] = tempPath;
}

void backTracking(int* nums, int numsSize, int* used) 
{
    //若path中元素个数等于nums元素个数，将nums放入ans中
    if(pathTop == numsSize) {
        copy();
        return;
    }
    int i;
    for(i = 0; i < numsSize; i++) {
        //若当前下标中元素已使用过，则跳过当前元素
        if(used[i])
            continue;
        used[i] = 1;
        path[pathTop++] = nums[i];
        backTracking(nums, numsSize, used);
        //回溯
        pathTop--;
        used[i] = 0;
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    //初始化辅助变量
    path = (int*)malloc(sizeof(int) * numsSize);
    ans = (int**)malloc(sizeof(int*) * 1000);
    int* used = (int*)malloc(sizeof(int) * numsSize);
    //将used数组中元素都置0
    initialize(used, numsSize);
    ansTop = pathTop = 0;

    backTracking(nums, numsSize, used);

    //设置path和ans数组的长度
    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = numsSize;
    }
    return ans;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64

    2.组合总和问题

    组合总和问题的分析：组合及每层选的值以及该值的左边所有值下一层则不能在被选择，为了控制选值，则需要startIndex来索引下标，并根据条件收集和返回结果。
    剪枝：剪枝操作要根据题目的收集结果条件进行剪枝，组合总和问题一般通过排序+和下一层的元素相加来剪枝，一般都在for循环的判断部分进行剪枝。

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

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

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

    问题分析：该问题为组合问题，数字为1-9，则代表数字有序，要收集相加和为n的k个整数集合，则不满足这个条件直接返回。

    int* result;
int rTop;
int aTop;


void BackTracking(int k, int n, int startIndex, int sum, int** arr)
{
    // - 剪枝
    if(rTop == k) 
    {
        if(sum == n) {
            int* tempPath = (int*)malloc(sizeof(int) * k);
            int j;
            for(j = 0; j < k; j++)
                tempPath[j] = result[j];
            arr[aTop++] = tempPath;
        }
        return;
    }
    // - 剪枝
    else if(rTop != k && sum >= n)
    {
        return;
    }
    for(int j = startIndex; j <=9; j++)
    {
        sum+=j;
        result[rTop++] = j;
        BackTracking(k,n,j+1,sum,arr);
        rTop--;
        // - 组合总和问题要注意每层回溯要-=结果数组内容。
        sum-=j;

    }


}

int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) 
{
    int** arr = (int**)malloc(sizeof(int*)*1000);
        //初始化辅助变量
    result = (int*)malloc(sizeof(int) * k);
    rTop = aTop = 0;

    BackTracking(k, n, 1, 0,arr);

    //设置返回的二维数组中元素个数为ansTop
    *returnSize = aTop;
    //设置二维数组中每个元素个数的大小为k
    *returnColumnSizes = (int*)malloc(sizeof(int) * aTop);
    int i;
    for(i = 0; i < aTop; i++) {
        (*returnColumnSizes)[i] = k;
    }
    return arr;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    剪枝：该题依旧对数量有限制，则可以用组合问题的剪纸方法进行剪枝

     for(int i = index; i <= 9 - (k-Top)+1; i++)

    • 1

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

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

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

    问题分析：该问题为组合问题，同一个数子课重复使用，找出和为target的值。

    int** arr;
int* result;
int rTop;
int aTop;
int* length;

void BackTracking(int sum, int target, int* candidates, int n, int startIndex)
{
    // - sum > target返回
    if(sum > target)
        return;
    // - 等于target收集数据
    if(sum == target)
    {
        int* tmp = (int*)malloc(sizeof(int)*rTop);
        for(int i = 0; i < rTop; i++)
        {
            tmp[i] = result[i];
        }
        arr[aTop] = tmp;
        length[aTop++] = rTop;
        return;
    }
    // - 改题目需要的是组合，所以不用遍历遍历过的
    for(int j = startIndex; j < n; j++)
    {
        
        sum+=candidates[j];
        result[rTop++] = candidates[j];
        BackTracking(sum,target,candidates,n,j);
        rTop--;
        // - sum 要-;
        sum-=candidates[j];

    }

}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) 
{
    length = (int*)malloc(sizeof(int)*200);
    arr = (int**)malloc(sizeof(int*)*1000);
    result = (int*)malloc(sizeof(int)*100);
    rTop = aTop = 0;
    int sum = 0;
    BackTracking(sum, target,candidates,candidatesSize,0);
    *returnSize = aTop;
    *returnColumnSizes = (int*)malloc(sizeof(int)*aTop);
      int i;
    for(i = 0; i < aTop; i++) {
        (*returnColumnSizes)[i] = length[i];
    }
    return arr;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    剪枝：只要某一层的和+下一层将要遍历的数大于target就不再进入循环。

    for (int i = startIndex; i < n && sum + candidates[i] <= target; i++)

    • 1

    3.分割字串问题

    分割字串问题的分析：**分割字串问题的本质在于选择分割位置，我们通过startIndex控制分割的起始位置，循环变量控制分割位置，分割过的位置不能在分割，会出现重复。

    分割回文串
    给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

    回文串 是正着读和反着读都一样的字符串。

    问题分析：该问题为分割字串问题，同时收集结果的条件为全部回文，[startIndex,i]是一个分割区间，只要整个串被分割完，则代表可以收集结果了。

    char*** arr;
char** result;
int aTop;
int rTop;
int* arrSize;

// - 判断回文
int checkStr(char* s, int start, int end)
{
    while(start <= end)
    {
        if(s[start] == s[end])
        {
            start++;
            end--;
        }
        else
        {
            return 0;
        }
    }
    return 1;


}

char* curStr(char* s, int start, int end)
{
    char* tmp = (char*)malloc(sizeof(char)*(end-start+2));
    int index = 0;
    for(int i = start; i <= end; i++)
    {
        tmp[index++] = s[i];
    }
    tmp[index] = '\0';

    return tmp;

}


void copy()
{
    char** tmp = (char**)malloc(sizeof(char*)*rTop);
    for(int i = 0; i < rTop; i++)
    {
        tmp[i] = result[i];
    }

    arrSize[aTop] = rTop;
    arr[aTop++] = tmp;


}
void BackTracking(char* s, int len, int startIndex)
{
    // startIndex >= strlen的时候收集结果
    if(startIndex >= len)
    { 
        copy();
        return ;
    }



    for(int j = startIndex; j < len; j++)
    {
        if(checkStr(s,startIndex,j))
        {
            result[rTop++] = curStr(s,startIndex,j);
        }
        // - 某层不回文，则++接着判断。
        else
            continue;
        BackTracking(s,len,j+1);

        rTop--;

    }

}

char*** partition(char* s, int* returnSize, int** returnColumnSizes)
{
    arrSize = (int*)malloc(sizeof(int)*40000);
    arr = (char***)malloc(sizeof(char**)*40000);
    int len = strlen(s);
    // - result数组存储的是满足条件的组合，该组合不会超过len个
    result = (char**)malloc(sizeof(char*)*len);
    rTop = aTop = 0;
    BackTracking(s,len,0);
    *returnSize = aTop;
    *returnColumnSizes = (int*)malloc(sizeof(int)*aTop);

    for(int i = 0; i < aTop; i++)
    {
        (*returnColumnSizes)[i] = arrSize[i];

    }
    return arr;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101

    复原IP地址
    有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

    例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
    给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

    问题分析：本题目为分割字串问题，分割条件为加每个ip地址都是有效，且要加入点号。

    char* result;
char** arr;
int rTop;
int aTop;

int isIPAdders(char* s, int start, int end)
{
    if(start > end)
        return 0;
    if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return 0;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
            return 0;
        }
        num = num * 10 + (s[i] - '0');
        if (num > 255) { // 如果大于255了不合法
            return 0;
        }
    }
    return 1;
}


void CurStr(char* s, int start, int end)
{
    for(int i = start; i <= end; i++)
    {
        result[rTop++] = s[i];
    }
}

void BackTracking(char* s, int len, int startIndex, int pointSize)
{
    if(pointSize == 3)
    {
        if(isIPAdders(s, startIndex, len-1))
        {
            char* tmp = (char*)malloc(sizeof(char)*(len+4));
            CurStr(s, startIndex, len-1);
            for(int i = 0; i <= rTop; i++)
            {
                tmp[i] = result[i];
            }
            tmp[rTop] = '\0';
            arr[aTop++] = tmp;
            // - 最后一次回退不能由循环完成，必须在这里完成，并且最后一个回退不用回退.号
            rTop-=((len-1)-startIndex+1);
            return;
        }
        return;
    }

                            // - 每个合法地址从startIndex开始最多3个字符，剪枝。
    for(int j = startIndex; j < 3+startIndex; j++)
    {
        if(isIPAdders(s,startIndex, j))
        {
            CurStr(s,startIndex,j);
            result[rTop++] = '.';
            pointSize++;

            BackTracking(s,len,j+1,pointSize);
            rTop-=(j-startIndex+2);
            pointSize--;
        }
        // - 只要起始位置不是合法地址，则该串就无法分割出合法地址。
        else
            break;

    }

}

// - 分割子串
char** restoreIpAddresses(char* s, int* returnSize) 
{
    int len = strlen(s);
    if(len < 4 && len > 12)
        return NULL;    
    arr = (char**)malloc(sizeof(char*)*10000);
    result = (char*)malloc(sizeof(char)*(len+4));
    rTop = aTop = 0;
    BackTracking(s,len,0,0);
    *returnSize = aTop;
    return arr;


}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    剪枝：每个分割项的数字个数是[1-3]，所以可以在for循环判断部分剪枝。

    for(int j = startIndex; j < 3+startIndex; j++)

    • 1

    4.子集问题

    子集问题的分析：子集问题的本质依旧是组合问题，不过收集条件为无，及收集所有结点，同时每次收集完不用返回。

    子集
    给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

    解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

    问题分析：本题为子集问题，则要收集所有结点。

    int** arr;
int* result;
int* length;
int rTop;
int aTop;

void copy()
{
    int* tmp = (int*)malloc(sizeof(int)*10);
    for(int i = 0; i < rTop; i++)
    {
        tmp[i] = result[i];
    }
    length[aTop] = rTop;
    arr[aTop++] = tmp;

}

// - 子集问题--收集所有回溯树的结点
void BackTracking(int* nums, int numsSize, int startIndex)
{
    copy();
	
	// - 没有元素可取，就返回。
    if(startIndex >= numsSize)
        return;

    for(int i = startIndex; i < numsSize; i++)
    {
        result[rTop++] = nums[i];
        BackTracking(nums,numsSize, i+1);
        rTop--;
    }

}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) 
{
    arr = (int**)malloc(sizeof(int*)*2000);
    result = (int*)malloc(sizeof(int)*numsSize);
    length = (int*)malloc(sizeof(int)*2000);
    rTop = aTop = 0;
    BackTracking(nums,numsSize,0);
    *returnSize = aTop;
    *returnColumnSizes = (int*)malloc(sizeof(int)*aTop);
    for(int i = 0; i < aTop; i++)
    {
        (*returnColumnSizes)[i] = length[i];
    }
    return arr;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    递增子序列
    给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

    数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

    问题分析：存在重复元素，并且要求返回不同递增子序列，则不能通过排序去重，可以使用hash表，记录每次选择的元素，完成去重操作，去重的原因在于重复的元素存在重复收集结果的情况，同时改题目也需要我们遍历所有结点，收集结果的条件是result数字的元素大于1。

    int** arr;
int* result;
int* length;
int rTop;
int aTop;

void copy()
{
    int* tmp = (int*)malloc(sizeof(int)*rTop);
    // for(int i = 0; i < rTop; i++)
    // {
    //     tmp[i] = result[i];
    // }
    memcpy(tmp, result, rTop*sizeof(int));
    length[aTop] = rTop;
    arr[aTop++] = tmp;

}


find(int* hash, int size, int element)
{
    int i;
    for(i = 0; i < size; i++) {
        if(hash[i] == element)
            return 1;
    }
    return 0;
}

// - 去重 - 不能用排序进行去重，因为要求原数组的递增子序列 -- 哈希表
void BackTracking(int* nums, int numsSize, int startIndex)
{
    if(rTop > 1)
        copy();
    
    // - 每层都生成一个哈希表，去重。
    int* hash = (int*)malloc(numsSize*sizeof(int));
    int hashTop = 0;
    for(int i = startIndex; i < numsSize; i++)
    {
    	// - 满足以下条件++，不收集结果。
        if((rTop > 0 && nums[i] < result[rTop-1]) || find(hash, numsSize,nums[i]))
            continue;
        result[rTop++] = nums[i];
        hash[hashTop++] = nums[i];
        BackTracking(nums,numsSize, i+1);
        rTop--;
    }

}

int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) 
{
    arr = (int**)malloc(sizeof(int*)*33000);
    result = (int*)malloc(sizeof(int)*numsSize);
    length = (int*)malloc(sizeof(int)*33000);
    rTop = aTop = 0;
    BackTracking(nums,numsSize,0);
    *returnSize = aTop;
    *returnColumnSizes = (int*)malloc(sizeof(int)*aTop);
    for(int i = 0; i < aTop; i++)
    {
        (*returnColumnSizes)[i] = length[i];
    }
    return arr;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
  • 相关阅读:
    FreeSql 导入数据的各种场景总结 [C#.NET ORM]
    使用Jmeter+ant进行接口自动化测试(数据驱动)
    HTTP协议
    Java @PreDestroy 注解的使用
    uni-app 分包
    【操作系统】Lesson1-什么是操作系统
    Elasticsearch优化
    Java技术学习|消息队列|初级RabbitMQ
    C++ Primer Plus 第七章笔记
    【深入浅出C#】章节10: 最佳实践和性能优化：性能调优和优化技巧
  • 原文地址：https://blog.csdn.net/reyas/article/details/134483759