46/47. Permutations I/II

Permutations I

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路: 典型的backtracking问题,在递归过程中,list中的元素不断变化,当list.size()等于nums.length的时候,这时候就是一个满足条件的排列组合,需要放入最终结果, 把结果加入最终res的时候要重新创建个新的list, res.add(new ArrayList(list));
复杂度: Time: O(n!), Space(n)

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) return res;
        helper(res, nums, new ArrayList<Integer>());
        return res;
    }
    public void helper (List<List<Integer>> res, int[] nums, List<Integer> list) {

        if (list.size() == nums.length) {
            if (!res.contains(list)) {
                res.add(new ArrayList<Integer>(list));
            }
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) continue;
            list.add(nums[i]);
            helper(res, nums, list);
            list.remove(list.size() - 1);
        }
    }
}

Permutations II

题目中给定的数字可能是重复的。 先对给定的数组中的元素进行排序, 这样重复的元素就会相邻。当我们再递归把元素放入list的时候,我们要判断当前元素有没有被用过,而且还要判断当前元素与数组中下一个元素是否相同,如果相同的话就要往下找,找到不同的元素为止。作为下一个元素插入到list当中。
所以我们再每次循环的时候要判断该位是否访问过 或者 前一位没有访问过的话,前一位元素是否跟后一位相同,我们需要找到不同的元素。

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        int size = nums.length;
        boolean[] used = new boolean[size];
        backtracking(res, new ArrayList<Integer>(), nums, used);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] used) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<Integer>(list));
            return;    
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i != 0 && !used[i - 1] && nums[i - 1] == nums[i] )) continue;
            list.add(nums[i]);
            used[i] = true;
            backtracking(res, list, nums, used);
            list.remove(list.size() - 1);
            used[i] = false;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s