class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > permute(vector<int> nums) {
        // write your code here
        vector<vector<int> > results;
        if (nums.size() == 0) {
            results.push_back(vector<int>());
            return results;
        }
        vector<bool> visited(nums.size(), false);
        vector<int> current;
        dfsHelper(nums, current, visited, results);
        return results;
    }
    // 1. definition: get a permutation of numbers from nums that have not been visited before and put them into current;
    void dfsHelper(vector<int>& nums, vector<int>& current, vector<bool>& visited, vector<vector<int> >& results) {
        if (current.size() == nums.size()) {
            results.push_back(current);
            return;
        }

        for(int i = 0; i < nums.size(); i++) {
            if (visited[i]) {
                continue;
            }
            // In permutation, a spot can be occupied by any element from the candidate vector; that's why we always loop from index 0 till the end of the candidate vector so that each element can get the chanced to be selected for current spot;
            current.push_back(nums[i]);
            visited[i] = true;
            dfsHelper(nums, current, visited, results);
            current.pop_back();
            visited[i] = false;
        }
    }
};