回溯算法

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

/**
 * 46.全排列
 * 链接：https://leetcode.cn/problems/permutations/submissions/
 * 思路：回溯算法
 * */
public class Solution {
    
    private List<List<Integer>> result;
    private boolean[] marked;
    private int[] permute;
    
    public List<List<Integer>> permute(int[] nums) {
        result = new ArrayList<>();
        marked = new boolean[nums.length];
        permute = new int[nums.length];
        backtrack(nums, 0);
        return result;
    }

    private void backtrack(int[] nums, int index) {
        if (index == nums.length) {
            result.add(copy(permute));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (marked[i]) {
                continue;
            }
            permute[index] = nums[i];
            marked[i] = true;
            backtrack(nums, index + 1);
            marked[i] = false;
        }
    }

    private List<Integer> copy(int[] permute) {
        List<Integer> list = new ArrayList<>();
        for (int num : permute) {
            list.add(num);
        }
        return list;
    }
}

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