本文主要是介绍LeetCode回溯算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. leetcode 77组合

//给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

模板一，利用used数组

List<List<Integer>> ans = new LinkedList<>();

        public List<List<Integer>> combine(int n, int k) {

            backTrace(n, k, 0,  new LinkedList<>(), new boolean[n + 1]);
            return ans;

        }

        private void backTrace(int n, int k,  int count, LinkedList<Integer> tmp, boolean[] used) {
            if (count == k) {
                ans.add(new LinkedList(tmp));
                return;
            }
            for (int i = 1; i <= n; i++) {
                if (!used[i]) {
                    used[i] = true;
                    tmp.addLast(i);
                    backTrace(i, k,  count + 1, tmp, used);
                    tmp.pollLast();
                    used[i] = false;
                }

            }
        }

模板2：不利用used数组，利用下标。

List<List<Integer>> ans = new LinkedList<>();

        public List<List<Integer>> combine(int n, int k) {

            backTrace(n, k, 0, 1, new LinkedList<>());
            return ans;

        }

        private void backTrace(int n, int k, int count, int start, LinkedList<Integer> tmp) {
            if (count == k) {
                ans.add(new LinkedList(tmp));
                return;
            }
            for (int i = start; i <= n; i++) {
                tmp.addLast(i);
                backTrace(n, k, count + 1, i + 1, tmp);
                tmp.pollLast();
            }

        }

这篇关于LeetCode回溯算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！