MENU

LeetCode46. 全排列

July 10, 2018 • Read: 181 • LeetCode

image
标准dfs问题,只不过这道题有点麻烦在于返回的是一个List嵌套List

声明一些变量,首先是ans保存最终结果,其次是path[],存储当前选取的元素的下标,然后是boolean v[],保存元素中某个下标的值是否用过,默认值是false,用过就置为true

dfs函数中首先进行边界条件判断,如果到了边界,就将所有保存在path中的下标对应的nums[]的值赋给一个List,然后return。其次i从0到nums.length枚举每一个下标,先进行判断,没有选过才选,将i的值给到path[idx],然后将当前的v[i]置为ture,在进行下一层的dfs(idx + 1,nums),最后是回溯,将v[i]变为false

class Solution {
    public static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public static int[] path = new int[100];
    public static boolean[] v = new boolean[100];
    public static void dfs(int idx,int[] nums) {
        if(idx >= nums.length) {
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i = 0;i < nums.length;i++)
                tmp.add(nums[path[i]]);
            ans.add(tmp);
            return;
        }
        for(int i = 0;i < nums.length;i++) {
            if(!v[i]) {
                path[idx] = i;
                v[i] = true;
                dfs(idx + 1,nums);
                v[i] = false;
            }
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        ans.clear();
        dfs(0,nums);
        return ans;
    }
}
最后编辑于: October 10, 2018
Archives Tip
QR Code for this page
Tipping QR Code