46 Permutations

Given a collection ofdistinctnumbers, 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]
]

Solution)

We can use a backtracking algorithm to find all possible combinations.

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        return backtrack(result, new ArrayList<Integer>(), nums, 0);
    }
    public List<List<Integer>> backtrack(List<List<Integer>> result, List<Integer> tmpList, int[] nums, int start) {
        if (start == nums.length) {
            result.add(new ArrayList<Integer>(tmpList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tmpList.contains(nums[i])) continue;
                tmpList.add(nums[i]);
                backtrack(result, tmpList, nums, start+1);
                tmpList.remove(tmpList.size()-1);
            }
        }
        return result;
    }
}