照着leetcode原题改的,这个case可以过,但是仅仅用curr_res == target来加入结果
感觉不够,必须要所有的数都visited。
public class Solution {
public static void main(String[] args) {
int[] nums = {1,2,3, 60, 7};
System.out.println(get(nums, 48));
}
public static List get(int[] nums, int target) {
List result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
boolean[] visited = new boolean[nums.length];
helper(nums, 0, 0, target, visited, "", result);
return result;
}
public static void helper(int[] nums, int prev_num, int curr_res,int
target, boolean[] visited, String path, List result) {
if (curr_res == target) {
result.add(new String(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
if (path.length() == 0) {
helper(nums, nums[i], nums[i], target, visited, path +
nums[i], result);
} else {
helper(nums, nums[i], curr_res + nums[i], target,
visited, path + "+" + nums[i], result);
helper(nums, -nums[i], curr_res - nums[i], target,
visited, path + "-" + nums[i], result);
helper(nums, prev_num * nums[i], curr_res - prev_num +
prev_num * nums[i], target, visited, path + "*" + nums[i], result);
helper(nums, prev_num / nums[i], curr_res - prev_num +
prev_num / nums[i],target, visited, path + "/" + nums[i], result);
}
visited[i] = false;
}
}
}
}
Output:[1+2*60/3+7, 1-2*3+60-7, 1-2*3-7+60, 1-3*2+60-7, 1-3*2-7+60, 1+60-2*3
-7, 1+60*2/3+7, 1+60-3*2-7, 1+60/3*2+7, 1+60-7-2*3, 1+60-7-3*2, 1*60-2-3-7,
1*60-2-7-3, 1*60-3-2-7, 1*60-3-7-2, 1*60-7-2-3, 1*60-7-3-2, 1*60/7*2*3, 1*60
/7*3*2, 1+7+2*60/3, 1+7+60*2/3, 1+7+60/3*2, 1-7-2*3+60, 1-7-3*2+60, 1-7+60-2
*3, 1-7+60-3*2, 2*60/3+1+7, 2*60/3+7+1, 3-1-2*7+60, 3-1+60-2*7, 3-1+60-7*2,
3-1-7*2+60, 3-2*7-1+60, 3-2*7+60-1, 3+60-1-2*7, 3+60-1-7*2, 3+60-2*7-1, 3+60
-7*2-1, 3-7*2-1+60, 3-7*2+60-1, 60+1-2*3-7, 60+1-3*2-7, 60+1-7-2*3, 60+1-7-3
*2, 60-1-2*7+3, 60-1*2-3-7, 60-1*2-7-3, 60-1+3-2*7, 60-1+3-7*2, 60-1*3-2-7,
60-1*3-7-2, 60-1-7*2+3, 60-1*7-2-3, 60-1*7-3-2, 60*1-2-3-7, 60*1-2-7-3, 60*1
-3-2-7, 60*1-3-7-2, 60*1-7-2-3, 60*1-7-3-2, 60*1/7*2*3, 60*1/7*3*2, 60/1-2-3
-7, 60/1-2-7-3, 60/1-3-2-7, 60/1-3-7-2, 60/1-7-2-3, 60/1-7-3-2, 60/1/7*2*3,
60/1/7*3*2, 60-2-1*3-7, 60-2-1*7-3, 60-2*1-3-7, 60-2*1-7-3, 60-2/1-3-7, 60-2
/1-7-3, 60-2-3-1*7, 60-2-3*1-7, 60-2-3/1-7, 60-2-3-7, 60-2*3+1-7, 60-2*3-7+1
, 60-2-7-1*3, 60-2-7*1-3, 60-2-7/1-3, 60-2-7-3, 60-2*7-1+3, 60-2*7+3-1, 60*2
/3+1+7, 60*2/3+7+1, 60+3-1-2*7, 60+3-1-7*2, 60+3-2*7-1, 60+3-7*2-1, 60-3-1*2
-7, 60-3-1*7-2, 60-3*1-2-7, 60-3*1-7-2, 60-3/1-2-7, 60-3/1-7-2, 60-3-2-1*7,
60-3-2*1-7, 60-3-2/1-7, 60-3-2-7, 60-3*2+1-7, 60-3*2-7+1, 60-3-7-1*2, 60-3-7
*1-2, 60-3-7/1-2, 60-3-7-2, 60/3*2+1+7, 60/3*2+7+1, 60-7+1-2*3, 60-7+1-3*2,
60-7-1*2-3, 60-7-1*3-2, 60-7*1-2-3, 60-7*1-3-2, 60-7/1-2-3, 60-7/1-3-2, 60-7
-2-1*3, 60-7-2*1-3, 60-7-2/1-3, 60-7-2-3, 60-7-2*3+1, 60-7*2-1+3, 60-7*2+3-1
, 60-7-3-1*2, 60-7-3*1-2, 60-7-3/1-2, 60-7-3-2, 60-7-3*2+1, 60/7*1*2*3, 60/7
*1*3*2, 60/7/1*2*3, 60/7/1*3*2, 60/7*2*1*3, 60/7*2/1*3, 60/7*2*3, 60/7*3*1*2
, 60/7*3/1*2, 60/7*3*2, 7+1+2*60/3, 7+1+60*2/3, 7+1+60/3*2, 7+2*60/3+1, 7+60
*2/3+1, 7+60/3*2+1]