leetcode 77. Combinations 按照index递归搜索+全排列做法

太过爱你忘了你带给我的痛 2022-06-08 02:11 132阅读 0赞

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,  
If n = 4 and k = 2, a solution is:

\[  
\[2,4\],  
\[3,4\],  
\[2,3\],  
\[1,2\],  
\[1,3\],  
\[1,4\],  
\]

这道题就是给出k个数组的所有的可能，是一道类似全排列的问题，直接递归解决，利用类似全排列的方法可以做到剪枝，要是一般的DFS可能要费时间。

建议和[leetcode 90. Subsets II DFS深度优先搜索 + 全排列][leetcode 90. Subsets II DFS_ _] 和 [leetcode 78. Subsets DFS深度优先搜索][leetcode 78. Subsets DFS] 一起学习

代码如下:

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution 
    {
        
    
        List<List<Integer>> res=new ArrayList<List<Integer>>();
    
        public List<List<Integer>> combine(int n, int k) 
        {
            if(n<=0 || k<=0 || k>n)
                return res;
            List<Integer> one=new ArrayList<>();
            getByDFS(n,k,1,one);
            return res;
        }
        /*
         *这个就是普通的DFS 
         * */
        private void getByDFS(int n, int k, int index, List<Integer> one)
        {
            if(index==n+1)
            {
                if(one.size()==k)
                    res.add(new ArrayList<>(one));
                return ;
            }else 
            {
                if(one.size()==k)
                {
                    res.add(new ArrayList<>(one));
                    return ;
                }else 
                {
                    getByDFS(n, k, index+1, one);
    
                    one.add(index);
                    getByDFS(n, k, index+1, one);
                    one.remove(one.size()-1);
                }
            }
        }
    
    
        /*
         * 很明显的递归问题，这个和全排列很像
         * 设置一个标志数组，记录选取的元素，
         * 这个要比直接DFS要好
         * */
        public List<List<Integer>> combine111(int n, int k) 
        {
            if(n<=0 || k<=0 || k>n)
                return res;
            boolean []flag=new boolean[n];
            getAllByDFS(k,n-k,flag,0);
            return res;
        }
    
        private void getAllByDFS(int has, int notHas,boolean[] flag, int index) 
        {
            if(index==flag.length)
            {
                List<Integer> one=new ArrayList<>();
                for(int i=0;i<flag.length;i++)
                {
                    if(flag[i])
                        one.add(i+1);
                }
                res.add(one);   
            }else
            {
                if(has>0)
                {
                    flag[index]=true;
                    getAllByDFS(has-1, notHas, flag, index+1);
                    flag[index]=false;
                }
    
                if(notHas>0)
                    getAllByDFS(has, notHas-1, flag, index+1);
            }
    
        }
    }

下面是C++的做法，就是一个经典的DFS深度优先遍历应用

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<vector<int>> res;
        vector<vector<int>> combine(int n, int k) 
        {
            if (n <= 0 || k <= 0 || k > n)
                return res;
    
            vector<int> one;
            getAllByDFS(n, k, 1, one);
            return res;
        }
    
        void getAllByDFS(int n, int k, int index, vector<int>& one)
        {
            if (index == n+1)
            {
                if (one.size() == k)
                    res.push_back(one);
                return;
            }
            else
            {
                if (one.size() == k)
                {
                    res.push_back(one);
                    return;
                }
                else
                {
                    getAllByDFS(n, k, index + 1, one);
    
                    one.push_back(index);
                    getAllByDFS(n, k, index + 1, one);
                    one.erase(one.end()-1);
                }
            }
        }
    };

[leetcode 90. Subsets II DFS_ _]: http://blog.csdn.net/jackzhang_123/article/details/77942940
[leetcode 78. Subsets DFS]: http://blog.csdn.net/jackzhang_123/article/details/77938096