leetcode77.组合Java

╰半橙微兮° 2024-04-18 07:33 39阅读 0赞

# LeetCode.77 组合 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

## 解法一：DFS+回溯法 ##

图解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]

代码：

package com.leetcode.solution;
    
    import java.util.*;
    
    /** * @Author : fanc * @Date : 2019-09-01 19:25 */
    public class Solution77 { 
        List<List<Integer>> output = new LinkedList<>();
        int n;
        int k;
    
        public void traceback(int first, LinkedList<Integer> current) { 
            if (current.size() == k) { 
                //错误，不能直接加上current，否则所有的元素都是一个引用
                //output.add(current);
                output.add(new LinkedList<Integer>(current));
                System.out.println(output);
                return;
            }
    
            for (int i = first; i <= n; i ++) { 
                //保存回溯结果
                //LinkedList<Integer> temp = new LinkedList<>(current);
                current.add(i);
                traceback(i + 1, current);
                //回溯：第一种方法current.removeLast()因为每一个add后面跟一个remove保证回溯
                //current = temp;
                current.removeLast();
            }
        }
    
        public List<List<Integer>> combine(int n, int k) { 
            this.n = n;
            this.k = k;
            traceback(1, new LinkedList<>());
            return output;
        }
    }

有两种回溯方法：

1.  保存current结果
2.  add之后然后remove，保证一对一

**需要注意的是，需要每次new一个list，防止每一个引用都一样，也就是需要有一个深拷贝的过程**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/4c14c58a0822403d9fd5e15afaaca479.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/bb975b70222445bcb0c5ef0f03c6e86c.png