ch8-of-programmercarl-1

• 77. 组合
  • 思路
  • 代码
• 216. 组合总和 III
  • 思路
  • 代码
• 17. 电话号码的字母组合
  • 思路
  • 代码
• 39. 组合总和
  • 思路
  • 代码
• 40. 组合总和 II
  • 思路
  • 代码
• 131. 分割回文串
  • 思路
  • 代码
• 93. 复原 IP 地址
  • 思路
  • 代码
• 78. 子集
  • 思路
  • 代码
• 90. 子集 II
  • 思路
  • 代码
• 491. 递增子序列
  • 思路
  • 代码
• 总结

1 组合

• 题目链接：77. 组合

1.1 题目描述

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

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

示例1:

输入: n = 4, k = 2
输出:
[
 [2,4],
 [3,4],
 [2,3],
 [1,2],
 [1,3],
 [1,4],
]

示例2:

输入: n = 1, k = 1
输出: [[1]]

1.2 思路

完整代码如下：

• Cpp实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void dfs(int n, int k, int startIndex){
        if(startIndex > n || path.size() == k){
            if(path.size() == k){
                res.emplace_back(path);
            }
            return;
        }else{
            for(int i = startIndex; i <= n; ++i){
                path.emplace_back(i);
                dfs(n, k, i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }
};

• C实现

int **ret, cnt = 0;
void backtracking(int n, int k, int startIndex, int *returnSize, int *tmp){
    if(cnt > k-1){
        ret[*returnSize] = (int *)malloc(sizeof(int)*k);
        for(int i = 0; i < cnt; i++){
            ret[*returnSize][i] = tmp[i];
        }
        (*returnSize)++;
        return;
    }else{
        for(int i = startIndex; i <= n; i++){
            tmp[cnt++] = i;
            backtracking(n, k, i+1, returnSize, tmp);
            cnt--;
        }
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
    int tmp[k];
    ret = (int **)malloc(sizeof(int*) * 10001);
    *returnSize = 0;
    backtracking(n, k, 1, returnSize, tmp);
    *returnColumnSizes = (int *)malloc(sizeof(int)*(*returnSize));
    for(int i = 0; i < (*returnSize); i++){
        (*returnColumnSizes)[i] = k;
    }
    return ret;
}

2 组合总和 III

• 题目链接：216. 组合总和 III

2.1 题目描述

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

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

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

示例1:

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

示例2:

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

示例3:

输入: k = 4, n = 1
输出: []

2.2 思路

完整代码如下：

• Cpp实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void dfs(int k, int n, int startIndex, int sum){
        if(startIndex > 10 || path.size() == k || sum == n){
            if(path.size() == k && sum == n){
                res.emplace_back(path);
            }
            return;
        }else{
            for(int i = startIndex; i < 10; ++i){
                path.emplace_back(i);
                dfs(k, n, i+1, sum + i);
                path.pop_back();
            }
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1, 0);
        return res;
    }
};

• C实现

int cnt = 0;
int **ret;
void backtracking(int k, int n, int startIndex, int sum, int *returnSize, int** returnColumnSizes, int* tmp){
    if(cnt > k-1 || sum > n){   //前一个条件为处理结果，后一个则是剪枝
        if(sum == n){           //判断是否满足要求
            ret[*returnSize] = (int *)malloc(sizeof(int)*k);
            for(int i = 0; i < cnt; i++){
                ret[*returnSize][i] = tmp[i];
            }
            (*returnSize)++;
        }
        return;
    }else{
        for(int i = startIndex; i < 10-(k-cnt)+1; i++){ //剪枝
            tmp[cnt++] = i;     //将当前值存入数组
            sum += i;           //用于判断当前暂存数组中的数是否为目标值n
            backtracking(k, n, i+1, sum, returnSize, returnColumnSizes, tmp);
            cnt--;              //回溯
            sum -= i;           //回溯
        }
    }
}

int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes){
    int tmp[k];
    ret = (int **)malloc(sizeof(int*) * 10001);
    *returnColumnSizes = (int *)malloc(sizeof(int)*10001);
    *returnSize = 0;
    backtracking(k, n, 1, 0, returnSize, returnColumnSizes, tmp);
    for(int i = 0; i < (*returnSize); i++){
        (*returnColumnSizes)[i] = k;
    }
    return ret;
}

3 17. 电话号码的字母组合

• 题目链接：17. 电话号码的字母组合 “17. 电话号码的字母组合”)

3.1 题目描述

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

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

示例1:

输入: digits = “23”
输出: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

示例2:

输入: digits = “”
输出: []

示例3:

输入: digits = “2”
输出: [“a”,”b”,”c”]

3.2 思路

完整代码如下：

• Cpp 实现

class Solution {
public:
    vector<string> str = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> res;
    string path;
    int n;
    void dfs(string digits, int r, int c){
        if(r == n){
            res.emplace_back(path);
            return;
        }else{
            for(int i = 0; i < str[digits[r]-'2'].length(); ++i){
                path += str[digits[r]-'2'][i];
                dfs(digits, r+1, i);
                path.pop_back();
            }
        }
    }
    vector<string> letterCombinations(string digits) {
        n = digits.length();
        if(n == 0) return res;
        dfs(digits, 0, 0);
        return res;
    }
};

• C 实现

char *list[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
char **ret;
char *path;
int n;
void dfs(char* digits, int r, int *returnSize){
    if(r == n){
        ret[*returnSize] = (char *)malloc(sizeof(char)*(n+1));
        for(int i = 0; i < n; i++){
            ret[*returnSize][i] = path[i];
        }
        ret[(*returnSize)++][n] = '\0';
        return;
    }else{
        for(int i = 0; i < strlen(list[digits[r]-'2']); ++i){
            path[r] = list[digits[r]-'2'][i];
            dfs(digits, r+1, returnSize);
        }
    }
}
char ** letterCombinations(char * digits, int* returnSize){
    n = strlen(digits);
    *returnSize = 0;
    ret = (char **)malloc(sizeof(char *)*10001);
    if(n == 0) return ret;
    path = (char *)malloc(sizeof(char) *(n+1));
    dfs(digits, 0, returnSize);
    free(path);
    return ret;
}

4 组合总和

• 题目链接：39. 组合总和

4.1 题目描述

给你一个 无重复元素 的整数数组 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
输出: []

4.2 思路

完整代码如下：

• Cpp 实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int size;

    void dfs(vector<int>& candidates, int startIndex, int sum, int target){
        if(startIndex >= size || sum >= target){
            if(sum == target){
                res.emplace_back(path);
            }
            return;
        }else{
            for(int i = startIndex; i < size; ++i){
                path.emplace_back(candidates[i]);
                dfs(candidates, i, sum + candidates[i], target);
                path.pop_back();
            }
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        size = candidates.size();
        dfs(candidates, 0, 0, target);
        return res;
    }
};

• C 实现

int cnt = 0, sum = 0;
int **ret;
void backtracking(int* candidates, int n, int target, int startIndex, int *returnSize, int** returnColumnSizes, int* tmp){
    if(sum >= target){  
        if(sum == target){
            ret[*returnSize] = (int *)malloc(sizeof(int)*500);
            for(int i = 0; i < cnt; i++){
                ret[*returnSize][i] = tmp[i];
            }
            (*returnColumnSizes)[*returnSize] = cnt;
            (*returnSize)+=1;
        } 
        return;
    }else{
        for(int i = startIndex; i < n; i++){
            tmp[cnt++] = candidates[i];
            sum += candidates[i];
            backtracking(candidates, n, target, i, returnSize, returnColumnSizes, tmp);
            cnt--;
            sum -= candidates[i];           
        }
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    ret = (int **)malloc(sizeof(int *)*10001);
    *returnColumnSizes = (int *)malloc(sizeof(int)*10001);
    *returnSize = 0;
    int tmp[500];
    backtracking(candidates, candidatesSize, target, 0, returnSize, returnColumnSizes, tmp);
    return ret;
}

5 组合总和 II

• 题目链接：40. 组合总和 II

5.1 题目描述

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例2:

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

5.2 思路

  这题与上一题的区别在于数组中的元素是有相同的而非单一的，所以在DFS的时候应当要处理元素值一样的问题。首先先对数组进行排序，然后进行DFS, 当当前循环的元素下标不为当前递归层中的第一个时且其与其前一个数一样时说明这个可以跳过。

完整代码如下：

• Cpp 实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int size;

    void dfs(vector<int>& candidates, int startIndex, int sum, int target){
        if(startIndex >= size || sum >= target){
            if(sum == target){
                res.emplace_back(path);
            }
            return;
        }else{
            for(int i = startIndex; i < size; ++i){
                if(i != startIndex && candidates[i] == candidates[i-1]) continue;
                path.emplace_back(candidates[i]);
                dfs(candidates, i+1, sum + candidates[i], target);
                path.pop_back();
            }
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        size = candidates.size();
        dfs(candidates, 0, 0, target);
        return res;
    }
};

• C 实现

int cnt = 0, sum = 0;
int **ret;
void backtracking(int* candidates, int n, int target, int startIndex, int *returnSize, int** returnColumnSizes, int* tmp){
    if(sum >= target){  
        if(sum == target){
            ret[*returnSize] = (int *)malloc(sizeof(int)*500);
            for(int i = 0; i < cnt; i++){
                ret[*returnSize][i] = tmp[i];
            }
            (*returnColumnSizes)[*returnSize] = cnt;
            (*returnSize)+=1;
        } 
        return;
    }else{
        for(int i = startIndex; i < n; i++){
            if(i>startIndex && candidates[i]==candidates[i-1]){
                continue;
            }
            tmp[cnt++] = candidates[i];
            sum += candidates[i];
            backtracking(candidates, n, target, i+1, returnSize, returnColumnSizes, tmp);
            cnt--;
            sum -= candidates[i];           
        }
    }
}

6 分割回文串

• 题目链接：131. 分割回文串

6.1 题目描述

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

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

示例1:

输入: s = “aab”
输出: [[“a”,”a”,”b”],[“aa”,”b”]]

示例2:

输入: s = “a”
输出: [[“a”]]

6.2 思路

  采用回溯+回文串判断即可。思路总体上同组合问题一致，只是这一题我们需要对每个子串判断是否为回文串。创建一个string变量用来存储单个子串，创建一个vector用于存放整个字符串分割成的子串，这里要注意，题目要求这个字符串分割后所有子串都要是回文串，因而单个子串分割后先判断是否为回文串，是再把这个子串插入到暂存vector中，当整个字符串分割完成后暂存vector中的串就都是回文串，直接将其插入到答案中即可。

  官方题解中采用动态规划预先对字符串进行处理，省去重复判断子串是否为回文串的步骤，大大降低时间复杂度。预处理如下;

for (int i = n - 1; i >= 0; --i) {
    for (int j = i + 1; j < n; ++j) {
        f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
    }
}

完整代码如下：

• Cpp 实现

class Solution {
public:
    vector<vector<string>> res;
    vector<string> tmp;
    int size;
    bool check(string s){
        int l = 0, r = s.length()-1;
        while(l < r){
            if(s[l++] != s[r--]){
                return false;
            }
        }
        return true;
    }

    void dfs(string s, int rest){
        if(rest == 0){
            for(auto s: tmp){
                if(!check(s)){
                    return;
                }
            }
            res.emplace_back(tmp);
            return;
        }else{
            string path;
            for(int i = size-rest; i < size; ++i){
                path += s[i];
                if(check(path)){
                    tmp.emplace_back(path);
                    dfs(s, size-i-1);
                    tmp.pop_back();
                }
            }
        }
    }

    vector<vector<string>> partition(string s) {
        size = s.length();
        dfs(s, size);
        return res;
    }
};

• C 实现

  C处理字符串太麻烦了，后边有空再补上。。。

7 复原 IP 地址

• 题目链接：93. 复原 IP 地址

7.1 题目描述

有效 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 中的任何数字。你可以按 任何 顺序返回答案。

示例1:

输入: s = “25525511135”
输出: [“255.255.11.135”,”255.255.111.35”]

示例2:

输入: s = “0000”
输出: [“0.0.0.0”]

示例3:

输入: s = “101023”
输出: [“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]

7.2 思路

  回溯+剪枝。

• 回溯：在string取若干位数字作为ip地址的一部分，然后进入下一层递归。由于ip地址由4个整数构成，每一个整数都位于0和255之间且不能有前缀0,因而每层递归中的循环设定为3，即最多取三位数。取完要对当前位整数进行判断，确定其是否在0和255之间以及是否有前缀0，判断函数如下：

  bool check(string s){
      int res = 0, len = s.length();
      if(len != 1 && s[0] == '0') return false; //确定是否有前缀0
      for(char ch: s){
          res *= 10;
          res += ch -'0';
      }
      return res < 256; //判断当前整数是否处于区间中
  }

• 剪枝：这里有两个可以优化的地方；

  • 首先是当前整数取完，剩余的字符串长度如果大于3倍的ip地址剩余位长度时，说明此时字符串太长了，无需进行下一层递归，要不就当前位继续取，要不就直接返回。
  • 第二就是剩余的部分刚好等于3倍的ip地址剩余位长度且下一位大于2，这种情况相当于ip地址剩余位的整数都是3三位数，如果下一位大于2则说明后面的已经超过上述的区间，无需进行下一层递归，要不就当前位继续取，要不就直接返回。

完整代码如下：

• Cpp 实现

class Solution {
public:
    vector<string> res;
    int size;
    
    bool check(string s){
        int res = 0, len = s.length();
        if(len != 1 && s[0] == '0') return false; //判断是否有前缀0
        for(char ch: s){
            res *= 10;
            res += ch -'0';
        }
        return res < 256;
    }

    void dfs(string s, int startIndex, string path, int cnt){
        if(startIndex == size ||  cnt == 4){         
            if(startIndex == size &&  cnt == 4){   //如果起始位不是最后一位说明字符串太长了
                res.emplace_back(path);
            }
            return;
        }else{
            string str = "";
            for(int i = 0; i < 3 && (startIndex + i) < size; ++i){
                str += s[startIndex + i];
                if(!check(str) 
                    || (size-startIndex-i-1)==3*(4-cnt)&&s[startIndex+i+1]>'2'  //剪枝1：后边必须取3位且下一位大于2
                    || (size-startIndex-i-1)>3*(4-cnt)){      //剪枝2：后边取3位字符串还有剩
                    continue;
                }
                if(path.size() == 0){
                    dfs(s, startIndex + i + 1, str, cnt+1);
                }else{
                    dfs(s, startIndex + i + 1, path + "." + str, cnt+1);
                }
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        size = s.length();
        if(size > 4*3) return res;
        dfs(s, 0, "", 0);
        return res;
    }
};

• C 实现

  C做字符串太烦人了，等有空再补上。

8 子集

• 题目链接：78. 子集

8.1 题目描述

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

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

示例1:

输入: nums = [1,2,3]
输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例2:

输入: nums = [0]
输出: [[],[0]]

8.2 思路

  直接回溯即可，和组合问题一个套路。

完整代码如下：

• Cpp 实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int size;
    void dfs(vector<int>& nums, int startIndex){
        if(startIndex == size){
            return;
        }else{
            for(int i = startIndex; i < size; ++i){
                path.emplace_back(nums[i]);
                res.emplace_back(path);
                dfs(nums, i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        size = nums.size();
        res.emplace_back(path);
        dfs(nums, 0);
        return res;
    }
};

• C 实现

int** res;
int* path;
int size;

void copy(int pathSize, int *returnSize, int **returnColumnSizes){
    res[*returnSize] = (int *)malloc(sizeof(int)*pathSize);
    (*returnColumnSizes)[*returnSize] = pathSize;
    for(int i = 0; i < pathSize; ++i){
        res[*returnSize][i] = path[i];
    }
    (*returnSize)++;
}

void dfs(int* nums, int startIndex, int pos, int* returnSize, int** returnColumnSizes){
    for(int i = startIndex; i < size; ++i){
        path[pos] = nums[i];
        copy(pos+1, returnSize, returnColumnSizes);
        dfs(nums, i+1, pos+1, returnSize, returnColumnSizes);
    }
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    size = numsSize;
    res = (int**)malloc(sizeof(int *)*1024);
    *returnColumnSizes = (int *)malloc(sizeof(int)*1024);
    *returnSize = 0;
    (*returnColumnSizes)[(*returnSize)++] = 0;

    path = (int *)malloc(sizeof(int)*10);
    dfs(nums, 0, 0, returnSize, returnColumnSizes);
    return res;
}

9 子集 II

• 题目链接：90. 子集 II

9.1 题目描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

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

示例1:

输入: nums = [1,2,2]
输出: [[],[1],[1,2],[1,2,2],[2],[2,2]]

示例2:

输入: nums = [0]
输出: [[],[0]]

9.2 思路

  这一题和上一题的思路一致，只是这一题没有了数组中的数字都是唯一的这个限制，因而需要对数组中的重复数字进行滤除，滤除方式和40. 组合总和 II是一致的，先排序，然后看是不是与上一个值相等，等于就跳过(前提是当前数字不是当前递归层的首个循环数)。

完整代码如下：

• Cpp 实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int size;

    void dfs(vector<int>& nums, int startIndex){
        if(startIndex == size){
            return;
        }else{
            for(int i = startIndex; i < size; ++i){
                if(i != startIndex && nums[i] == nums[i-1]){  //滤去重复数字
                    continue;
                }
                path.emplace_back(nums[i]);
                res.emplace_back(path);
                dfs(nums, i+1);
                path.pop_back();
            }
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        size = nums.size();
        sort(nums.begin(), nums.end()); //先排序
        res.emplace_back(path);
        dfs(nums, 0);
        return res;
    }
};

• C 实现

int** res;
int* path;
int size;

void copy(int pathSize, int *returnSize, int **returnColumnSizes){
    res[*returnSize] = (int *)malloc(sizeof(int)*pathSize);
    (*returnColumnSizes)[*returnSize] = pathSize;
    for(int i = 0; i < pathSize; ++i){
        res[*returnSize][i] = path[i];
    }
    (*returnSize)++;
}

void dfs(int* nums, int startIndex, int pos, int* returnSize, int** returnColumnSizes){
    for(int i = startIndex; i < size; ++i){
        if(i != startIndex && nums[i] == nums[i-1]){  //滤去重复数字
            continue;
        }
        path[pos] = nums[i];
        copy(pos+1, returnSize, returnColumnSizes);
        dfs(nums, i+1, pos+1, returnSize, returnColumnSizes);
    }
}

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

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    size = numsSize;
    res = (int**)malloc(sizeof(int *)*1024);
    *returnColumnSizes = (int *)malloc(sizeof(int)*1024);
    *returnSize = 0;
    (*returnColumnSizes)[(*returnSize)++] = 0;
    if(size == 0) return res;

    qsort(nums, size, sizeof(int), cmp);  //排序
    path = (int *)malloc(sizeof(int)*10);
    dfs(nums, 0, 0, returnSize, returnColumnSizes);
    return res;
}

10 递增子序列

• 题目链接：491. 递增子序列

10.1 题目描述

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

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

示例1:

输入: [4,6,7,7]
输出: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例2:

输入: nums = [4,4,3,2,1]
输出: [[4,4]]

10.2 思路

  这一题类似上一题，也是需要去重。但是这一题由于是要求原数组中的递增子序列，因而不能改变该数组（也就是不能像上一题一样直接排序然后去重）。这里采用一个哈希表来记录当前层已经用过的数字，然后循环中如果检测到当前层已经用过当前遍历的数字，则跳过这个数字。注意，哈希表应该在单层递归中定义，不能定义为全局，因为当前层用过哪个数字是不影响下一层的。

完整代码如下：

• Cpp 实现

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int size;

    void dfs(vector<int>& nums, int startIndex){
        if(path.size() > 1){  //当暂存数组中size大于1时说明是一个答案，插到答案中
            res.emplace_back(path);
        }
        bool used[201] = {0}; //哈希表，初始化为false
        for(int i = startIndex; i < size; ++i){
            if(used[nums[i]+100] || !path.empty() && nums[i] < path.back()){  
                continue;     //检测是否用过该数字以及当前数字加入后是否还是递增的
            }
            used[nums[i]+100] = true; //已经访问过该数字，哈希置为true
            path.emplace_back(nums[i]);
            dfs(nums, i+1);
            path.pop_back();
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        size = nums.size();
        dfs(nums, 0);
        return res;
    }
};

• C 实现

int** res;
int* path;
int size;

void copy(int pathSize, int *returnSize, int **returnColumnSizes){
    res[*returnSize] = (int *)malloc(sizeof(int)*pathSize);
    (*returnColumnSizes)[*returnSize] = pathSize;
    for(int i = 0; i < pathSize; ++i){
        res[*returnSize][i] = path[i];
    }
    (*returnSize)++;
}

void dfs(int* nums, int startIndex, int pos, int* returnSize, int** returnColumnSizes){
    if(pos > 1){
        copy(pos, returnSize, returnColumnSizes);
    }
    bool used[201] = {0};
    for(int i = startIndex; i < size; ++i){
        if(used[nums[i]+100] || (pos>0 && path[pos-1] > nums[i])){ 
            continue;
        }
        used[nums[i]+100] = true;
        path[pos] = nums[i];
        dfs(nums, i+1, pos+1, returnSize, returnColumnSizes);
    }
}


int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    size = numsSize;
    res = (int**)malloc(sizeof(int *)*32768);
    *returnColumnSizes = (int *)malloc(sizeof(int)*32768);
    *returnSize = 0;
    if(size == 0) return res;

    path = (int *)malloc(sizeof(int)*15);
    dfs(nums, 0, 0, returnSize, returnColumnSizes);
    return res;
}

总结