有的时候题目想不出来,或者只能用搜索来解决(如Leetcode – 39题),我们就可以用排列/组合搜索答案。下面的排列与组合模板都使用DFS来实现,非常易懂且方便记忆。

1. 排列

方法private void permutation(int[] arr, int depth, int[] curr, boolean[] visited, List<int[]> result)实现了求arr的所有排列,并且将结果保存的result中。depth表示目前正在填充curr的第几位,visited数组记录了之前已经访问的元素。在for循环中,我们遍历每个之前没有访问过位置,并在visited标记为true,防止下一次递归调用访问同一元素。当depth达到数组arr的长度时,我们复制curr的内容到result中。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private void permutation(int[] arr, int depth, int[] curr, boolean[] visited, List<int[]> result) {
        if (depth == arr.length)
            result.add(Arrays.copyOf(curr, curr.length));

        for (int i = 0; i < arr.length; i++) {
            // 这里我们用要visited数组标记已访问的元素,防止重复下一次递归调用重复访问
            if (!visited[i]) {
                visited[i] = true;
                // 这里不需要回溯curr,因为下一次循环会覆盖curr[depth]
                curr[depth] = arr[i];
                permutation(arr, depth + 1, curr, visited, result);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<int[]> result = new ArrayList<>();
        int[] arr = new int[]{1, 2, 3};

        solution.permutation(arr, 0, new int[arr.length], new boolean[arr.length], result);

        for (int[] item : result) {
            System.out.println(Arrays.toString(item));
        }
    }
}
输出:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

2. 组合

这里的组合指的是从n个元素中挑选c个元素,而不考虑元素的顺序。方法void combination(int[] arr, int depth, int start, int[] curr, List<int[]> result)实现了从arr中挑选|curr|个元素。depth表示我们正在填充curr的第几位,start参数表明我们从arr中第几个位置开始挑选元素。与排列算法相比,我们不需要visited数组。因为我们总是从start之后挑选元素,所以不会出现挑选重复元素的情况。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private void combination(int[] arr, int depth, int start, int[] curr, List<int[]> result) {
        if (depth == curr.length) {
            result.add(Arrays.copyOf(curr, curr.length));
            return;
        }

        for (int i = start; i < arr.length; i++) {
            curr[depth] = arr[i];
            combination(arr, depth + 1, i + 1, curr, result);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<int[]> result = new ArrayList<>();
        int[] arr = new int[]{1, 2, 3};

        solution.combination(arr, 0, 0, new int[2], result);

        for (int[] item : result) {
            System.out.println(Arrays.toString(item));
        }
    }
}
输出:
[1, 2]
[1, 3]
[2, 3]
pwrliang Combination, Permutation , , ,

Leave a Reply

Your email address will not be published. Required fields are marked *