# JAVA SOLUTION BY USING BFS

• My Idea:
Try every possible special offer, using mem to memorize all the states, finally iterate all the states to find out the minimal value.

``````      public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
Map<String, Integer> mem = new HashMap<>();
mem.put(listToStr(needs), 0);

Queue<List<Integer>> queue = new LinkedList<>();
queue.offer(needs);
while (!queue.isEmpty()) {
List<Integer> aux = queue.poll();
for (List<Integer> spec : special) {
boolean isValid = true;
for (int i = 0; i < aux.size(); ++i) {
if (spec.get(i) > aux.get(i))
isValid = false;
}
if (isValid) {
List<Integer> remain = new ArrayList<>();
for (int i = 0; i < aux.size(); ++i) {
remain.add(aux.get(i) - spec.get(i));
}
mem.put(listToStr(remain), Math.min(mem.get(listToStr(aux)) + spec.get(spec.size() - 1),
mem.containsKey(listToStr(remain)) ? mem.get(listToStr(remain)) : 1 << 30));
queue.offer(remain);
}
}
}

int minValue = 1 << 30;
for (String key : mem.keySet()) {
int[] remain = strToList(key);
int sum = mem.get(key);
for (int i = 0; i < remain.length; ++i) {
sum += (remain[i] * price.get(i));
}
minValue = Math.min(minValue, sum);
}
return minValue;
}

private String listToStr(List<Integer> needs) {
StringBuilder sb = new StringBuilder();
for (Integer need : needs) {
sb.append(need + "+");
}
return sb.toString().substring(0, sb.length() - 1);
}

private int[] strToList(String str) {
String[] nums = str.split("\\+");
int[] needs = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
needs[i] = Integer.parseInt(nums[i]);
}
return needs;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.