用swap swap的办法求解。
这里是Java的一点不好的地方，我要把int[] nums 用在Arrays.asList上， 必须得把它先转成Integer[].
也可以不转，就不用Arrays.asList,就直接一个个加进结果里面就好了 。
Java版本
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Integer[] numsInteger = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
numsInteger[i] = nums[i];
}
permuteHelper(ans, numsInteger, 0);
return ans;
}
private void permuteHelper(List<List<Integer>> ans, Integer[] nums, int index) {
if (index == nums.length) {
ans.add(new ArrayList<>(Arrays.asList(nums)));
return;
}
for (int i = index; i < nums.length; i++) {
swap(nums, i, index);
permuteHelper(ans, nums, index + 1);
swap(nums, i, index);
}
}
private void swap(Integer[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
C++版本
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
dfs(nums, ans, 0);
return ans;
}
private:
void dfs(vector<int>& nums, vector<vector<int>>& ans, int index) {
if (index == nums.size() - 1) {
ans.emplace_back(nums);
return;
}
for (int i = index; i < nums.size(); i++) {
swap(nums[i], nums[index]);
dfs(nums, ans, index + 1);
swap(nums[i], nums[index]);
}
}
};
