[Algo Rhythm🕺💃] LeetCode 46. Permutations

📚 Problem description

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

 

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

 

🎯 Solution

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    
    public List<List<Integer>> permute(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        
        backtrack(nums, visited, new ArrayList<Integer>());
        
        return ans;
    }
    
    public void backtrack(int[] nums, boolean[] visited, List<Integer> list) {
        if(list.size() == nums.length) {
            ans.add(new ArrayList<Integer>(list));
            return;
        }
        
        for(int i = 0; i < nums.length; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                list.add(nums[i]);
                
                backtrack(nums, visited, list);
                
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }
        
    }
}

 

🧐 Approach

Permutation is one of typical example of backtracking. Backtracking is simply branching under specific condition.

If we think each element as node, branching condition is that node should not be visited.

Here is illustrated example.

 

📖  What I learned

When solving problem related with backtracking, think about branching condition!