[LeetCode] Combinations 组合项

r囧r小猫 2022-04-14 03:30 156阅读 0赞

## 问题 ##

这是一个组合问题:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70][]

## 图形化表述 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1][]

## 代码: ##

import java.util.List;
    import java.util.ArrayList;
    import java.util.LinkedList;
    
    /// 77. Combinations
    /// https://leetcode.com/problems/combinations/description/
    /// 时间复杂度: O(n^k)
    /// 空间复杂度: O(k)
    public class liubobo_8_3 {
    
        private ArrayList<List<Integer>> res;
    
        public List<List<Integer>> combine(int n, int k) {
    
            res = new ArrayList<List<Integer>>();
            if(n <= 0 || k <= 0 || k > n)
                return res;
    
            LinkedList<Integer> c = new LinkedList<Integer>();
            generateCombinations(n, k, 1, c);
    
            return res;
        }
    
        // 求解C(n,k), 当前已经找到的组合存储在c中, 需要从start开始搜索新的元素
        private void generateCombinations(int n, int k, int start, LinkedList<Integer> c){
    
            if(c.size() == k){
                res.add((List<Integer>)c.clone());
                return;
            }
    
            for(int i = start ; i <= n ; i ++){
                c.addLast(i);
                generateCombinations(n, k, i + 1, c);
                c.removeLast();
            }
    
            return;
        }
    
        private static void printList(List<Integer> list){
            for(Integer e: list)
                System.out.print(e + " ");
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            List<List<Integer>> res = (new liubobo_8_3()).combine(4, 2);
            for(List<Integer> list: res)
                printList(list);
        }
    }

## 感受: ##

本题和Permutations 全排列问题看似类似,其实还是有很多差别,  可以从核心代码的比较上看出来

Permutations:

private void generatePermutation(int\[\] nums, int index, LinkedList<Integer> p)\{

if(index == nums.length)\{//递归终止条件  
            res.add((LinkedList<Integer>)p.clone());  
            return;  
        \}

>         for(int i = 0 ; i < nums.length ; i ++)  
>             if(!used\[i\])\{//元素userd\[i\]没有被使用  
>                 used\[i\] = true;//使用了第i个元素  
>                 p.addLast(nums\[i\]);  
>                 generatePermutation(nums, index + 1, p );  
>                 p.removeLast();//删除最后的元素,这是题目性质问题,所谓的元素间在打仗  
>                 used\[i\] = false;//注意实际元素数组是和userd\[\]数组绑定的,所以删除也要同时处理  
>             \}

return;  
    \}

Combinations:  
private void generateCombinations(int n, int k, int start, LinkedList<Integer> c)\{

if(c.size() == k)\{  
            res.add((List<Integer>)c.clone());  
            return;  
        \}

for(int i = start ; i <= n ; i ++)\{  
            c.addLast(i);  
            generateCombinations(n, k, i + 1, c);  
            c.removeLast();  
        \}

return;  
    \}

**从代码逻辑上还是极其相似的,但主要不同的又在哪呢?**

答案在于userd\[\]上的使用 ,看出来了吧

if(!used[i]){//元素userd[i]没有被使用
    
         used[i] = true;//使用了第i个元素
    
        .....
    
         used[i] = false;//注意实际元素数组是和userd[]数组绑定的,所以删除也要同时处理
    
     }

如果将上面的userd相关删除

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 2][]

得到的结果:

无used\[\]         有used\[\]

1 1 1                1 2 3   
1 1 2                1 3 2   
1 1 3                2 1 3   
1 2 1                2 3 1   
1 2 2                3 1 2  
1 2 3                3 2 1   
1 3 1   
1 3 2   
1 3 3   
2 1 1   
2 1 2   
2 1 3   
2 2 1   
2 2 2   
2 2 3   
2 3 1   
2 3 2   
2 3 3   
3 1 1   
3 1 2   
3 1 3   
3 2 1   
3 2 2   
3 2 3   
3 3 1   
3 3 2   
3 3 3

最后造成了遍历上的差异

**Permutations                                                                                 Combinations**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 3][]           ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70]: /images/20220414/ea1f45ff34a1437db7e2726265442209.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1]: /images/20220414/d6d2a769927f4d969b947f46664e513b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 2]: /images/20220414/64ee7a1b17da4c729933a98c50387a23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20181123175340350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx,size_16,color_FFFFFF,t_70