for循环里的递归

发表于   |   分类于   |     |   阅读次数

目录

[toc]

17 电话号码的字母组合（回到目录）

定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

不对应任何字母。

示例:

1
2
3
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

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
class Solution {//使用递归回溯做法。非常妙！
public:
    
    vector<string> letterCombinations(string digits) 
    {
        vector<string> res;
        if(digits.size()==0) return res;
        string local;
        vector<vector<char> > table{{'w'}, {'w'}, {'a','b','c'}, {'d','e','f'}, {'g','h','i'}, {'j','k','l'}, 
        {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};//前两个，随便定义。。。。
        generate(table,res,local,0,digits);
        return res;
    }
private:
    void generate(vector<vector<char> > &table,vector<string> &res,string &local,int index,string digits)
    {
        int digit=digits[index]-'0';
        if(index==digits.size())
        {
            res.push_back(local);
        }
        for(int i=0;i<table[digit].size();i++)
        {
            local.push_back(table[digit][i]);
            generate(table,res,local,index+1,digits);
            local.pop_back();
        }
    }
};

==大坑==：
实际上这行代码是省略了的，因为对于一个字符串来说，结束符是‘\0’,index加到最后面递归函数自然会return，所以可以不用return。我一开始，是直接在res.push_back(local);的下一行加return，那肯定是错的。因为index还没大于digits.size，就不能return.

39 组合总和 I（回到目录）

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

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
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        sort(candidates.begin(),candidates.end());
        vector<vector<int> >res;
        vector<int> item;
        generate(candidates,res,item,target,0);
        return res;
        
        
    }
    void generate(vector<int> &candidates,vector<vector<int> > &res,vector<int> &item,int target,int begin)
    {
        int len=candidates.size();
        if(target==0)
        {
            res.push_back(item);
            return;
        }
        if(target<0) return;
        for(int i=begin;i<len;i++)
        {
            item.push_back(candidates[i]);
            generate(candidates,res,item,target-candidates[i],i);
            item.pop_back();
        }
    }
};

40 组合总和 II（回到目录）

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

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

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

方法1

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
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) 
    {
        vector<vector<int>> res;
        sort(num.begin(),num.end());
        vector<int> local;
        findCombination(res, 0, target, local, num);
        return res;
    }
    void findCombination(vector<vector<int>>& res, const int start, const int target, vector<int>& local, const vector<int>& num)
    {
        if(target==0)
        {
            res.push_back(local);
            return;
        }
        else
        {
            for(int i = start;i<num.size();i++) // iterative component
            {
                if(target<0) return;
                if(num[i]==num[i-1] && i>start) continue; // check duplicate combination
                local.push_back(num[i]),
                findCombination(res,i+1,target-num[i],local,num); // recursive componenet
                local.pop_back();
            }
        }
    }
};

另一种做法:使用set容器，代码和上面那题一样的

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
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) 
    {
        set<vector<int>> res;
        sort(num.begin(),num.end());
        vector<int> local;
        findCombination(res, 0, target, local, num);
        return vector<vector<int> > (res.begin(),res.end());
    }
    void findCombination(set<vector<int>>& res, const int order, const int target, vector<int>& local, const vector<int>& num)
    {
        if(target==0)
        {
            res.insert(local);
            return;
        }
        else
        {
            for(int i = order;i<num.size();i++) // iterative component
            {
                if(target<0) return;
                //if(num[i]==num[i-1]&&i>order) continue; // check duplicate combination
                local.push_back(num[i]),
                findCombination(res,i+1,target-num[i],local,num); // recursive componenet
                local.pop_back();
            }
        }
    }
};

46 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
11
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {//递归
public:
    vector<vector<int>> permute(vector<int>& nums) 
    {
        vector<vector<int> > res;
        generate(nums,res,0);
        return res;
    }
private:
    void generate(vector<int> &nums,vector<vector<int> >&res,int begin)
    {
        if(begin>=nums.size())
        {
            res.push_back(nums);
            return;
        }
        for(int i=begin;i<nums.size();i++)//循环实现和begin+1之后的全排列
        {
            swap(nums[begin],nums[i]);
            generate(nums,res,begin+1);
            swap(nums[begin],nums[i]);
        }
    }
};

注：我们来仔细推敲一下循环体里的代码，当我们对序列进行交换之后，就将交换后的序列除去第一个元素放入到下一次递归中去了，递归完成了再进行下一次循环。这是某一次循环程序所做的工作，这里有一个问题，那就是在进入到下一次循环时，序列是被改变了。可是，如果我们要假定第一位的所有可能性的话，那么，就必须是在建立在这些序列的初始状态一致的情况下,所以每次交换后，要还原，确保初始状态一致。

47 全排列II（回到目录）

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
8
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        vector<vector<int> >res;
        set<vector<int> > res_set;
        sort(nums.begin(),nums.end());
        generate(res,res_set,nums,0);
        return res;
    }
private:
    void generate(vector<vector<int> > &res,set<vector<int> > &res_set,vector<int> &nums,int begin)
    {
        if(begin>=nums.size() && res_set.find(nums) ==res_set.end())
        {
            res.push_back(nums);
            res_set.insert(nums);
            return;
        }
        for(int i=begin;i<nums.size();i++)
        {
            swap(nums[begin],nums[i]);
            generate(res,res_set,nums,begin+1);
            swap(nums[begin],nums[i]);
            
        }
    }
};

77 组合（回到目录）

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

1
2
3
4
5
6
7
8
9
10
11
输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

递归回溯

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
class Solution {
public:
    vector<vector<int>> combine(int n, int k) 
    {
        vector<vector<int> >res;
        vector<int> item(0,k);
        if(k>n) return res;
        generate(n,k,0,0,item,res);
        return res;
    }
private:
    void generate(int n,int k,int numOfDigit,int begin,vector<int> &item,vector<vector<int> > &res)
    {
        if(numOfDigit==k)
        {
            res.push_back(item);
            return;
        }   
        for(int i=begin;i<n;i++)
        {
            item.push_back(i+1);
            generate(n,k,numOfDigit+1,i+1,item,res);
            item.pop_back();
        }
    }
};

78 子集（回到目录）

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

小象写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
    vector<vector<int> >subsets(vector<int> &nums)
    {
        vector<vector<int> > result;
        vector<int> item;
        result.push_back(item);
        generate(0,nums,item,result);
        return result;
    }
private:
    void generate(int i,vector<int> &nums,vector<int> &item, vector<vector<int> >&result)
    {
        if(i>=nums.size()) return;
        item.push_back(nums[i]);
        result.push_back(item);
        generate(i+1,nums,item,result);
        item.pop_back();
        generate(i+1,nums,item,result);
    }
};

for循环里递归

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
class Solution {//for循环
public:
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<vector<int> >res;
        vector<int> item;
        res.push_back(item);
        sort(nums.begin(),nums.end());//解答错误不是没有排序的问题
        generate(res,item,nums,0);
        
        return res;
    }
private:
    void generate(vector<vector<int> > &res, vector<int> &item, vector<int> &nums, int begin)
    {
        if(begin>=nums.size())
        {
            return;
        }
        for(int i=begin;i<nums.size();i++)
        {
            item.push_back(nums[i]);
            res.push_back(item);
            generate(res,item,nums,i+1);
            item.pop_back();
        }
    }
};

90 子集 II（回到目录）

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

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

小象解法：

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
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        vector<vector<int> >result;
        vector<int> item;
        set<vector<int> > res_set;
        sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,nums,item,result,res_set);
        return result;
        
    }
private:
    void generate(int i, vector<int> &nums,vector<int> & item, vector<vector<int> > &result, set<vector<int> > &res_set)
    {
        if(i>=nums.size())
            return;
        item.push_back(nums[i]);
        
        if(res_set.find(item)==res_set.end())
        {
            result.push_back(item);
            res_set.insert(item);
        }
        generate(i+1,nums,item,result,res_set);
        item.pop_back();
        generate(i+1,nums,item,result,res_set);
    }
    
};

for循环里面递归

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
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        vector<vector<int> >res;
        vector<int> item;
        res.push_back(item);
        sort(nums.begin(),nums.end());//解答错误不是没有排序的问题
        generate(res,item,nums,0);
        
        return res;
    }
private:
    void generate(vector<vector<int> > &res, vector<int> &item, vector<int> &nums, int begin)
    {
        if(begin>=nums.size())
        {
            return;
        }
        for(int i=begin;i<nums.size();i++)
        {
            item.push_back(nums[i]);
            res.push_back(item);
            generate(res,item,nums,i+1);
            item.pop_back();
            while(i+1<nums.size() && nums[i]==nums[i+1]) i++;
        }
    }
};

131 分割回文串（回到目录）

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

1
2
3
4
5
6
输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

这是一道需要用DFS来解的题目，既然题目要求找到所有可能拆分成回文数的情况，那么肯定是所有的情况都要遍历到，对于每一个子字符串都要分别判断一次是不是回文数，那么肯定有一个判断回文数的子函数，还需要一个DFS函数用来递归，再加上原本的这个函数，总共需要三个函数来求解。代码如下：

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
class Solution {//循环里有递归
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> out;
        partitionDFS(s, 0, out, res);
        return res;
    }
    void partitionDFS(string s, int start, vector<string> &out, vector<vector<string>> &res) {
        if (start == s.size()) {
            res.push_back(out);
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            if (isPalindrome(s, start, i)) {
                out.push_back(s.substr(start, i - start + 1));
                partitionDFS(s, i + 1, out, res);
                out.pop_back();
            }
        }
    }
    bool isPalindrome(string s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) return false;
            ++start;
            --end;
        }
        return true;
    }
};

注：那么，对原字符串的所有子字符串的访问顺序是什么呢，如果原字符串是 abcd, 那么访问顺序为:a -> b -> c -> d -> cd -> bc -> bcd-> ab -> abc -> abcd, 这是对于没有两个或两个以上子回文串的情况。那么假如原字符串是aabc，那么访问顺序为：a -> a -> b -> c -> bc -> ab -> abc -> aa -> b -> c -> bc -> aab -> aabc，中间当检测到aa时候，发现是回文串，那么对于剩下的bc当做一个新串来检测，于是有b -> c -> bc，这样扫描了所有情况，即可得出最终答案。

-------------本文结束感谢您的阅读-------------
您的小小鼓励，是我不断更新的强大动力！