回溯算法-求子集-彻底理解子集去重问题

一般来说，只要有递归，就涉及回溯。
回溯其实是纯暴力的搜索，并非一个高效的算法。
回溯通常可以抽象成n叉树。

回溯能解决哪些问题：
1.组合问题。
2.切割问题。（如字符串切割）
3.子集问题。
4.排列问题。（“排列”强调元素的顺序，“组合”不强调顺序）
5.棋盘问题。

“去重”为什么很难理解呢？
所谓“去重”，其实就是使用过的元素不能重复选取。 这么一说好像很简单。
但是呢，很多同学在“去重”的问题上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂先把题目过了再说。
组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解“去重”的根本原因。

主要代码如下：

问题解决思路：
/*
1.如果nums元素都不相同，最多会有2的length次幂的返回值。
2.从示例[1,2,2]里可以看出，输出结果里包含[1,2,2]，也就是说,纵向是可以重复的，但[1,2]只有一个，也就说横向重复值，不能重复记录。(那纵向的重复值，该如何判断呢？)
3.先做一个nums从小到大的排序，原因是为了方便去重时候的比较。
4.区分清楚索引index和当前长度currLen的关系。索引是索引，每次dfs传入当前索引位置+1，currLen用一个单独的变量计算。
*/

int Compare(void const *a, void const *b)
{
    return *(int *)a - *(int *)b;
}

void dfs(int index, int currLen, int *nums, int numsSize, int *returnSize, int ** returnColumnSizes, int *record, int **res)
{    
    res[*returnSize] = calloc(currLen, sizeof(int));
    memcpy(res[*returnSize], record, sizeof(int) * currLen);
    (*returnColumnSizes)[*returnSize] = currLen;
    (*returnSize)++; 

    for (int i = index; i < numsSize; i++) { // 这句话太重要了：int i = index
        // 要去重，而且是横向去重（纵向的是可以有重复元素的，如[1,2,2], [2,2]）,但是在横向遍历的过程中，要pass掉重复的
        if (i > index && nums[i] == nums[i - 1]) { // 注意这里是i > index, 我开始写成了 i > 0,导致错误
            continue; // 此题与78题的差异就在这里的去重判断，横向去重
        }
        record[currLen] = nums[i];
        // 首位参数i + 1,也就是索引，传的是当前索引的下一个索引位置！ 第二个参数是当前record的长度，每次递归，长度也加一。
        dfs(i + 1, currLen + 1, nums, numsSize, returnSize, returnColumnSizes, record, res); 
 
    }

    return;
}

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int maxLen = pow(2, numsSize);
    int **res = calloc(maxLen, sizeof(int *));
    *returnSize = 0;
    *returnColumnSizes = calloc(maxLen, sizeof(int));

    int record[10] = { 0 };
    int recordLen = 0;
    qsort(nums, numsSize, sizeof(int), Compare);

    dfs(0, recordLen, nums, numsSize, returnSize, returnColumnSizes, record, res);

    return res;
}

参考B站“代码随想录”视频资料：
带你学透回溯算法（理论篇）
参考题目：
90. 子集 II