题目:输入一个含有8个数字的数组,判断有没有可能把这8个数字分别放在正方体的8个顶点上,使得正方体上三组相对的面上的4个顶点的和都相等。
解法:和全排列思路一样,只是最后多加一个判断条件:先确定第一个数字,然后对后面的数字做全排列。当所有数字都确定下来后,判断当前数组是否满足条件正方体上三组相对的面上的4个顶点的和都相等
,即
(nums[0] + nums[1] + nums[2] + nums[3] == nums[5] + nums[6] + nums[7] + nums[4]) && (nums[0] + nums[2] + nums[4] + nums[6] == nums[5] + nums[1] + nums[7] + nums[3]) && (nums[0] + nums[1] + nums[4] + nums[5] == nums[2] + nums[6] + nums[7] + nums[3])
private List<List<Integer>> Permutation(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length != 8) return result;
permutation(result, nums, 0);
return result;
}
private void permutation(List<List<Integer>> result, int[] nums, int index) {
if (index >= nums.length) {
if ((nums[0] + nums[1] + nums[2] + nums[3] == nums[5] + nums[6] + nums[7] + nums[4]) &&
(nums[0] + nums[2] + nums[4] + nums[6] == nums[5] + nums[1] + nums[7] + nums[3]) &&
(nums[0] + nums[1] + nums[4] + nums[5] == nums[2] + nums[6] + nums[7] + nums[3])) {
List<Integer> numbers = new ArrayList<>();
for (int num : nums) {
numbers.add(num);
}
result.add(numbers);
}
} else {
for (int i = index; i < nums.length; ++i) {
if (i == index || nums[i] != nums[index]) {
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
permutation(result, nums, index + 1);
temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
}
}
}