good source

Return values:

• true: if it is possible to generate the target_value by summing the elements in the array.
• false: if it is not possible.

Samples

Sample 1

can_sum(7, [5, 3, 4, 7]) -> true

because there are three possible solutions: 3+4, 4+3 and 7.

Sample 2

can_sum(7, [2, 4]) -> false

because it's impossible to build a 7 with the numbers in the array.

The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the target_sum, then return null.

If there are multiple combinations, return any af those.

Problem

The function shall return the number of possible ways to travel through a n x m grid from the top left corner to the bottom right corner.

Limit

It is only allowed to move:

• Down
• Right

Complexity

• O(2^(n + m)) time
• O(n + m) space

improve the time complexity from O(2^n) to O(n) by memoizing with a hash_set.

getting a value from the hash map fails.

to insert an element with a key and a value and not just the key.

This is a follow up of: grid traveler brute force approach

Problem

The program shall return the number of possible ways to travel through a n x m grid from the top left corner to the bottom right corner.

Limit

It is only allowed to move:

• Down
• Right

Complexity

• O(n*m) time
• O(n *m) space

The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the target_sum, then return null.

If there are multiple combinations, return any of those.

Use memoization to improve the time complexity of the brute-force approach from issue #17

to fibonacci.c

This is an improvement of can_sum brute force

Return values:

• true: if it is possible to generate the target_value by summing the elements in the array.
• false: if it is not possible.

Samples

Sample 1

can_sum(7, (int[]){ 5, 3, 4, 7 }, 4) -> true

because there are three possible solutions: 3+4, 4+3 and 7.

Sample 2

can_sum(7, { 2, 4 }, 2) -> false

because it's impossible to build a 7 with the numbers in the array.

Sample 3

can_sum(300, (int[]){ 7,  4 }, 2) -> false

this function call would take a really long time with a bad time complexity.

Bug

Program finds keys that were not inserted.

Console output

Source Code grid_traveler.c

Folder with all necessary files

#define _CRT_SECURE_NO_WARNINGS
#include "grid_traveler.h"
#include "khash.h"
#include <assert.h>
#include <stdio.h>
#include <stdbool.h>
//#define KEY_IN_HASH_MAP (it != kh_end(map_ptr) && kh_str_hash_func(key) == kh_str_hash_func(kh_key(map_ptr, it)))
#define KEY_BUFFER_SIZE 15u

KHASH_MAP_INIT_STR(map, long long)
khash_t(map)* map_ptr; 
khiter_t it;
int ret;
long long val;

void init_grid_traveler(void) {
	map_ptr = kh_init(map);
	it = -1;
	ret = -1;
	val = -1;
}

long long grid_traveler(int row, int column) {
	char key[KEY_BUFFER_SIZE], found_key[KEY_BUFFER_SIZE];
	sprintf(key, "<%d , %d>", row, column);
	printf("ENTERED recursive function with key: %s\n", key);
	if (row == 1 && column == 1) {
		puts("return 1;");
		return 1;
	} 
	if (row == 0 || column == 0) {
		puts("return 0;");
		return 0;
	}
	
	
	it = kh_get(map, map_ptr, key);
	int key_hash, found_key_hash;
	if (it != kh_end(map_ptr)) {
		sprintf(found_key, "%s", kh_key(map_ptr, it));
		key_hash = kh_str_hash_func(key);
		found_key_hash = kh_str_hash_func(found_key);
	}
	
	bool KEY_IN_HASH_MAP = (it != kh_end(map_ptr) && kh_str_hash_func(key) == kh_str_hash_func(kh_key(map_ptr, it)));
	if (KEY_IN_HASH_MAP) {
		printf("Key %s / found key %s found in hash_map with the value %lld\n", key, kh_key(map_ptr, it), kh_val(map_ptr, it));
		return kh_val(map_ptr, it);
	}
	else {
		val = grid_traveler(row - 1, column) + grid_traveler(row, column - 1);
		it = kh_put(map, map_ptr, key, &ret);
		assert(ret != -1);
		kh_val(map_ptr, it) = val;
		printf("Key %s value was CALCULATED: %lld and inserted into the hash_map with the key: %s\n", key, kh_val(map_ptr, it), kh_key(map_ptr, it));
	}
	return kh_val(map_ptr, it);
}

void deinit_grid_traveler(void) {
	free(map_ptr);
}