【CSDN 每日一练 ★★☆】【回溯】组合

【CSDN 每日一练 ★★☆】【回溯】组合

回溯

题目

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

示例

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

思路

*　DSF + 回溯

实现

import java.util.*;
public class Solution77 {
    List<List<Integer>> output = new LinkedList<>();
    int n;
    int k;
    public void traceback(int first, LinkedList<Integer> current) {
        // 当current==k时，表示得到结果的一种组合
        if (current.size() == k) {
            output.add(new LinkedList<Integer>(current));
            System.out.println(output);
            return;
        }
        // 从first 到 n中随机选一个，继续DSF
        for (int i = first; i <= n; i++) {
            current.add(i);
            traceback(i + 1, current);
            current.removeLast();
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        traceback(1, new LinkedList<>());
        return output;
    }
}