Algorithm

[LeetCode 46] Permutations[Java]

顿搜

2018-01-09

0 评论

767 阅读

正在检测是否收录...

01/09

1. Description

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

2. 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]
]

3. Code

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class LeetCode0046 {
    public List> permute(int[] nums) {
        List> result = new ArrayList>();
        if (nums == null) {
            return result;
        }

        HashSet set = new HashSet();

        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }

        dfs(nums, set, new ArrayList(), result);
        return result;
    }

    private void dfs(int[] nums, HashSet set, List current, List> result) {
        if (set.size() == 0) {
            result.add(new ArrayList(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                current.add(nums[i]);
                set.remove(nums[i]);
                dfs(nums, set, current, result);
                set.add(nums[i]);
                current.remove(current.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        LeetCode0046 leetcode = new LeetCode0046();
        List> result = leetcode.permute(new int[] { 1, 2, 3 });
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
}

DFS

朗读